Induction and Recursion - Hoang Anh Duc - MIM - HUS - VNU

Work 19.

• Solve the following recurrence relations with the given initial conditions and prove that the formula you found is correct using mathematical induction:

\[\begin{aligned}[t] (a) \quad a_n &= -a_{n-1}, a_0 = 5 \qquad & (e) \quad a_n &= 2a_{n-1} - 3, a_0 = -1 \quad \\[5pt] (b) \quad a_n &= a_{n-1} + 3, a_0 = 1 \qquad & (f) \quad a_n &= (n+1)a_{n-1}, a_0 = 2 \quad \\[5pt] (c) \quad a_n &= a_{n-1} - n, a_0 = 4 \qquad & (g) \quad a_n &= 2n a_{n-1}, a_0 = 3 \quad \\[5pt] (d) \quad a_n &= 5a_{n-1}, a_0 = 1 \qquad & (h) \quad a_n &= -a_{n-1} + n - 1, a_0 = 7 \quad \end{aligned}\]

• \((a) \quad a_n = -a_{n-1}, a_0 = 5\)

\[\begin{align} & \text{We form a conjecture using forward substitution:} \quad \\[5pt] & \text{Given recurrence relation: } \quad a_n = -a_{n-1}, a_0 = 5 \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad a_0 = 5 \quad \\[5pt] & ● \quad a_1 = -a_0 = -5 \quad \\[5pt] & ● \quad a_2 = -a_1 = -(-5) = 5 \quad \\[5pt] & ● \quad a_3 = -a_2 = -5 \quad \\[5pt] & ● \quad a_4 = -a_3 = -(-5) = 5 \quad \\[8pt] & \text{From our calculation, we form the conjecture:} \quad \\[5pt] & \qquad a_n = (-1)^n \cdot 5 \quad \\[8pt] & \text{Now we prove our conjecture with mathematical induction:} \quad \\[5pt] & \text{Let P(n) = } a_n = (-1)^n \cdot 5 , \forall n \in \mathbb{N} \quad \\[5pt] & \text{Basis step: } a_0 = (-1)^0 \cdot 5 = 5 \text{ so P(0) = } \mathbf{T} \quad \\[5pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[5pt] & P(k) = a_k = (-1)^k \cdot 5 = \mathbf{T}, k \in \mathbb{N} \quad \\[10pt] & \text{Consider: } \quad \\[5pt] & P(k+1) = a_{k+1} = -a_k \overset{IH}{\mathrel{=}} -((-1)^k \cdot 5) = (-1)^{k+1} \cdot 5 \quad \\[5pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• \((b) \quad a_n = a_{n-1} + 3, a_0 = 1\)

\[\begin{align} & \text{We form a conjecture using backward substitution:} \quad \\[5pt] & \text{Given recurrence relation: } \quad a_n = a_{n-1} + 3, a_0 = 1 \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad a_n = a_{n-1} + 3 \quad \\[5pt] & ● \quad a_n = (a_{n-2} + 3) + 3 = a_{n-2} + 3 \cdot 2 \quad \\[5pt] & ● \quad a_n = (a_{n-3} + 3) + 3 \cdot 2 = a_{n-3} + 3 \cdot 3 \quad \\[5pt] & \qquad \vdots \quad \\[7pt] & ● \quad a_n = a_0 + 3 \cdot n = 1 + 3 \cdot n \quad \\[5pt] & \text{From our calculation, we form the conjecture:} \quad \\[5pt] & \qquad a_n = 1 + 3 \cdot n \quad \\[8pt] & \text{Now we prove our conjecture with mathematical induction:} \quad \\[5pt] & \text{Let P(n) = } a_n = 1 + 3 \cdot n , \forall n \in \mathbb{N} \quad \\[5pt] & \text{Basis step: } a_0 = 1 + 3 \cdot 0 = 1 \text{ so P(0) = } \mathbf{T} \quad \\[5pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[5pt] & P(k) = a_k = 1 + 3 \cdot k = \mathbf{T}, k \in \mathbb{N} \quad \\[10pt] & \text{Consider: } \quad \\[5pt] & P(k+1) = a_{k+1} = a_k + 3 \overset{IH}{\mathrel{=}} 1 + 3 \cdot k + 3 = 1 + 3(k + 1) \quad \\[5pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• \((c) \quad a_n = a_{n-1} - n, a_0 = 4\)

\[\begin{align} & \text{We form a conjecture using backward substitution:} \quad \\[5pt] & \text{Given recurrence relation: } \quad a_n = a_{n-1} - n, a_0 = 4 \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad a_n = a_{n-1} - n \quad \\[5pt] & ● \quad a_n = (a_{n-2} - (n - 1)) - n = a_{n-2} - (n - 1) - n \quad \\[5pt] & ● \quad a_n = (a_{n-3} - (n - 2)) - (n - 1) - n = a_{n-3} - (n - 2) - (n - 1) - n \quad \\[5pt] & \qquad \vdots \quad \\[7pt] & ● \quad a_n = a_0 - (1 + 2 + 3 + \ldots + n) = 4 - (1 + 2 + 3 + \ldots + n) \quad \\[8pt] & \text{From our calculation, we form the conjecture:} \quad \\[8pt] & \qquad a_n = 4 - \sum_{i=1}^{n} i = 4 - \frac{n(n+1)}{2} \quad \\[8pt] & \text{Now we prove our conjecture with mathematical induction:} \quad \\[8pt] & \text{Let P(n) = } 4 - \frac{n(n+1)}{2} , \forall n \in \mathbb{N} \quad \\[8pt] & \text{Basis step: } a_0 = 4 - \frac{0(0+1)}{2} = 4 \text{ so P(0) = } \mathbf{T} \quad \\[8pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[8pt] & P(k) = a_k = 4 - \frac{k(k+1)}{2} = \mathbf{T}, k \in \mathbb{N} \quad \\[10pt] & \text{Consider: } \quad \\[8pt] & P(k+1) = a_{k+1} = a_k - (k + 1) \overset{IH}{\mathrel{=}} \left( 4 - \frac{k(k+1)}{2} \right) - (k + 1) \quad \\[8pt] & \qquad \qquad = 4 - \left(\frac{k(k+1)}{2} + (k + 1)\right) = 4 - \left( \frac{k(k+1) + 2(k+1)}{2} \right) \quad \\[8pt] & \qquad \qquad = 4 - \frac{(k+1)(k+2)}{2} \quad \\[8pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• \((d) \quad a_n = 5a_{n-1}, a_0 = 1\)

\[\begin{align} & \text{We form a conjecture using forward substitution:} \quad \\[5pt] & \text{Given recurrence relation: } \quad a_n = 5a_{n-1}, a_0 = 1\quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad a_0 = 1 \quad \\[5pt] & ● \quad a_1 = 5a_0 = 5 \cdot 1 = 5 \quad \\[5pt] & ● \quad a_2 = 5a_1 = 5 \cdot 5 = 25 \quad \\[5pt] & ● \quad a_3 = 5a_2 = 5 \cdot 25 = 125 \quad \\[5pt] & ● \quad a_4 = 5a_3 = 5 \cdot 125 = 625 \quad \\[8pt] & \text{From our calculation, we form the conjecture:} \quad \\[5pt] & \qquad a_n = 5^n \quad \\[8pt] & \text{Now we prove our conjecture with mathematical induction:} \quad \\[5pt] & \text{Let P(n) = } a_n = 5^n , \forall n \in \mathbb{N} \quad \\[5pt] & \text{Basis step: } a_0 = 5^0 = 1 \text{ so P(0) = } \mathbf{T} \quad \\[5pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[5pt] & P(k) = a_k = 5^k = \mathbf{T}, k \in \mathbb{N} \quad \\[10pt] & \text{Consider: } \quad \\[5pt] & P(k+1) = a_{k+1} = 5a_k \overset{IH}{\mathrel{=}} 5(5^k) = 5 \cdot 5^k = 5^{k+1} \quad \\[5pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• \((e) \quad a_n = 2a_{n-1} - 3, a_0 = -1\)

\[\begin{align} & \text{We form a conjecture using backward substitution:} \quad \\[5pt] & \text{Given recurrence relation: } \quad a_n = 2a_{n-1} - 3, a_0 = -1 \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad a_n = 2a_{n-1} - 3 \quad \\[5pt] & ● \quad a_n = 2(2a_{n-2} - 3) - 3 = 4a_{n-2} - 9 \quad \\[5pt] & ● \quad a_n = 4(2a_{n-3} - 3) - 9 = 8a_{n-3} - 21 \quad \\[5pt] & ● \quad a_n = 8(2a_{n-4} - 3) - 21 = 16a_{n-4} - 45 \quad \\[5pt] & ● \quad a_n = 16(2a_{n-5} - 3) - 45 = 32a_{n-5} - 93 \quad \\[8pt] & \text{So far, our conjecture follows the form: } a_n = \mathbf{A}_na_0 - \mathbf{B}_n \quad \\[5pt] & \text{We can see that } \mathbf{A} \text{ are powers of 2, so we have: } a_n = 2^na_0 - \mathbf{B}_n \quad \\[5pt] & \text{Now we analyze } \mathbf{B} \text{:} \quad \\[8pt] & ● \quad B_1 - B_0 = 3 - 0 = 3 \quad \\[5pt] & ● \quad B_2 - B_1 = 9 - 3 = 6 \quad \\[5pt] & ● \quad B_3 - B_2 = 21 - 9 = 12 \quad \\[5pt] & ● \quad B_4 - B_3 = 45 - 21 = 24 \quad \\[5pt] & ● \quad B_5 - B_4 = 93 - 45 = 48 \quad \\[8pt] & \text{We can see that the differences } B_{i+1} - B_i = 3 \cdot 2^i, i \in \mathbb{N} \quad \\[5pt] & \text{Therefore, we formulate } B_n = 3 \cdot 2^n - 3 = 3(2^n - 1) \quad \\[5pt] & \text{From our calculation, we form the conjecture:} \quad \\[5pt] & \qquad a_n = 2^na_0 - 3(2^n-1) = (-1) \cdot 2^n - 3(2^n-1) \quad \\[8pt] & \text{Now we prove our conjecture with mathematical induction:} \quad \\[5pt] & \text{Let P(n) = } a_n = (-1) \cdot 2^n - 3(2^n-1) , \forall n \in \mathbb{N} \quad \\[5pt] & \text{Basis step: } a_0 = (-1) \cdot 2^0 - 3(2^0-1) = (-1) \cdot 1 - 3 \cdot 0 = -1 \text{ so P(0) = } \mathbf{T} \quad \\[5pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[5pt] & P(k) = a_k = (-1) \cdot 2^k - 3(2^k-1) = \mathbf{T}, k \in \mathbb{N} \quad \\[8pt] & \text{Consider: } \quad \\[5pt] & P(k+1) = a_{k+1} = 2a_k - 3 \overset{IH}{\mathrel{=}} 2((-1) \cdot 2^k - 3(2^k-1))-3 \quad \\[5pt] & \qquad \qquad = (-1) \cdot 2^{k+1} - 3 \cdot 2 (2^k - 1) - 3 \quad \\[5pt] & \qquad \qquad = (-1) \cdot 2^{k+1} - 3(2 \cdot 2^k - 2 + 1) \quad \\[5pt] & \qquad \qquad = (-1) \cdot 2^{k+1} - 3(2^{k + 1} - 1) \quad \\[8pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• \((f) \quad a_n = (n+1)a_{n-1}, a_0 = 2\)

\[\begin{align} & \text{We form a conjecture using forward substitution:} \quad \\[5pt] & \text{Given recurrence relation: } \quad a_n = (n+1)a_{n-1}, a_0 = 2 \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad a_0 = 2 \quad \\[5pt] & ● \quad a_1 = 2 \cdot 2 = 4 \quad \\[5pt] & ● \quad a_2 = 3 \cdot 4 = 2 \cdot 2 \cdot 3 = 12 \quad \\[5pt] & ● \quad a_3 = 4 \cdot 12 = 2 \cdot 2 \cdot 3 \cdot 4 = 48 \quad \\[5pt] & ● \quad a_4 = 5 \cdot 48 = 2 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 240 \quad \\[8pt] & \text{From our calculation, we form the conjecture:} \quad \\[5pt] & \qquad a_n = 2 (n + 1)! \quad (not \space a_n = 2 \cdot n! \text{ because n starts from 0})\quad \\[8pt] & \text{Now we prove our conjecture with mathematical induction:} \quad \\[5pt] & \text{Let P(n) = } a_n = 2 (n + 1)! , \forall n \in \mathbb{N} \quad \\[5pt] & \text{Basis step: } a_0 = 2 \cdot 1! = 2 \text{ so P(0) = } \mathbf{T} \quad \\[5pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[5pt] & P(k) = a_k = 2 (k + 1)! = \mathbf{T}, k \in \mathbb{N} \quad \\[10pt] & \text{Consider: } \quad \\[5pt] & P(k+1) = a_{k+1} = (k+1+1) a_k \overset{IH}{\mathrel{=}} (k+2) 2 (k + 1)! \quad \\[7pt] & \qquad \qquad = 2 (k+2)(k+1)! = 2 (k+2)! = 2 ((k+1)+1)! \quad \\[6pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• \((g) \quad a_n = 2n a_{n-1}, a_0 = 3\)

\[\begin{align} & \text{We form a conjecture using forward substitution:} \quad \\[5pt] & \text{Given recurrence relation: } \quad a_n = 2n a_{n-1}, a_0 = 3 \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad a_0 = 3 \quad \\[5pt] & ● \quad a_1 = 2 \cdot 1 \cdot 3 = 3 \cdot 2 \cdot 1 = 6 \quad \\[5pt] & ● \quad a_2 = 2 \cdot 2 \cdot 6 = 3 \cdot 4 \cdot 1 \cdot 2 = 3 \cdot 2^2 \cdot 2! = 24 \quad \\[5pt] & ● \quad a_3 = 2 \cdot 3 \cdot 24 = 3 \cdot 8 \cdot 1 \cdot 2 \cdot 3 = 3 \cdot 2^3 \cdot 3! = 144 \quad \\[5pt] & ● \quad a_4 = 2 \cdot 4 \cdot 144 = 3 \cdot 16 \cdot 1 \cdot 2 \cdot 3 \cdot 4 = 3 \cdot 2^4 \cdot 4! = 1152 \quad \\[8pt] & \text{From our calculation, we form the conjecture:} \quad \\[5pt] & \qquad a_n = a_0 \cdot 2^n \cdot n! = 3 \cdot 2^n \cdot n! \quad \\[8pt] & \text{Now we prove our conjecture with mathematical induction:} \quad \\[5pt] & \text{Let P(n) = } a_n = 3 \cdot 2^n \cdot n! , \forall n \in \mathbb{N} \quad \\[5pt] & \text{Basis step: } a_0 = 3 \cdot 2^0 \cdot 0! = 3 \cdot 1 \cdot 1 = 3 \text{ so P(0) = } \mathbf{T} \quad \\[5pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[5pt] & P(k) = a_k = 3 \cdot 2^k \cdot k! = \mathbf{T}, k \in \mathbb{N} \quad \\[10pt] & \text{Consider: } \quad \\[5pt] & P(k+1) = a_{k+1} = 2(k+1) a_k \overset{IH}{\mathrel{=}} 2(k+1) 3 \cdot 2^k \cdot k! \quad \\[5pt] & \qquad \qquad = 3 \cdot 2 \cdot 2^k (k+1)k! = 3 \cdot 2^{k+1} (k+1)! \quad \\[5pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• \((h) \quad a_n = -a_{n-1} + n - 1, a_0 = 7\)

\[\begin{align} & \text{Given recurrence relation: } \quad a_n = -a_{n-1} + n - 1, a_0 = 7 \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] \end{align}\]

\[\begin{aligned}[t] ● \quad a_0 &= 7 \qquad & ● \quad a_4 &= -(-6) + 4 - 1 = 9 \quad \\[5pt] ● \quad a_1 &= -7 + 1 - 1 = -7 \qquad & ● \quad a_5 &= -9 + 5 - 1 = -5 \quad \\[5pt] ● \quad a_2 &= -(-7) + 2 - 1 = 8 \qquad & ● \quad a_6 &= -(-5) + 6 - 1 = 10 \quad \\[5pt] ● \quad a_3 &= -8 + 3 - 1 = -6 \qquad & ● \quad a_7 &= -10 + 7 - 1 = -4 \quad \end{aligned}\]

\[\begin{align} & \text{We can see that when n is even, then:} \quad \\[5pt] & \exists \space i \in \mathbb{N} \text{ such that } a_n = a_i = 7 + i , n \text{ is even } \mid n \in \mathbb{N} \quad \\[5pt] & \text{When n is odd, we can see that:} \quad \\[5pt] & \exists \space i \geq 1 \mid i \in \mathbb{N} \text{ such that } a_n = a_i = -7 + i -1, n \text{ is odd } \mid n \in \mathbb{N} \quad \\[5pt] & \text{Therefore, we form the conjecture:} \quad \\[5pt]\ & a_n = \begin{cases} 7 + \frac{n}{2} & \text{if } n \text{ is even} \quad \\[7pt] -7 + \frac{n - 1}{2} & \text{if } n \text{ is odd} \end{cases} \\[10pt] & \quad \space = \begin{cases} \frac{14+n}{2} & \text{if } n \text{ is even} \quad \\[7pt] \frac{-15+n}{2} & \text{if } n \text{ is odd} \end{cases} \\[7pt] & \text{We can rewrite the conjecture } as^{(*)} \quad \\[8pt] & a_n = \frac{1-(-1)^n}{2} \cdot \frac{-15 + n}{2} + \frac{1+(-1)^n}{2} \cdot \frac{14 + n}{2} \quad \\[10pt] & \quad \space = \frac{-15+n+15(-1)^n-n(-1)^n}{4} + \frac{14+n+14(-1)^n+n(-1)^n}{4} \quad \\[10pt] & \quad \space = \frac{29(-1)^n+2n-1}{4} \quad \end{align}\]

\[\begin{align} & \text{Now we prove our conjecture with mathematical induction:} \quad \\[10pt] & \text{Let P(n) = } a_n = \frac{29(-1)^n+2n-1}{4} , \forall n \in \mathbb{N} \quad \\[10pt] & \text{Basis step: } a_0 = \frac{29(-1)^0+2\cdot0-1}{4} = 7 \text{ so P(0) = } \mathbf{T} \quad \\[10pt] & \text{Inductive step: Assume Inductive Hypothesis:} \quad \\[10pt] & P(k) = a_k = \frac{29(-1)^k+2k-1}{4} = \mathbf{T}, k \in \mathbb{N} \quad \\[10pt] & \text{Consider: } \quad \\[10pt] & P(k+1) = a_{k+1} = -a_k + (k + 1) - 1 \overset{IH}{\mathrel{=}} - \frac{29(-1)^k+2k-1}{4} + k \quad \\[10pt] & \qquad \qquad = \frac{-29(-1)^k-2k+1+4k}{4} = \frac{29(-1)^{k+1}+2(k+1)-1}{4} \quad \\[10pt] & \text{So } P(k) = \mathbf{T} \implies P(k+1) = \mathbf{T} \quad \\[5pt] & \text{Therefore, by mathematical induction, } P(n) = \mathbf{T}, \forall n \in \mathbb{N} \quad \end{align}\]

• Note: If you’re confused of the step at (*):

Work 20.

• Complete the following:

\[\begin{align} & \text{Let the world population in 2023 be 8 billion} \quad \\[5pt] & \text{and assume it increases at a rate of 0.8} \% \text{ per year. For n ≥ 1:} \quad \\[8pt] & \quad \text{(a) Construct a recurrence relation} \quad \\[5pt] & \text{to calculate the world population n years after 2023.}\quad \\[5pt] & \quad \text{(b) Derive an explicit formula to calculate} \quad \\[5pt] & \text{the world population n years after 2023.} \quad \\[5pt] & \quad \text{(c) What will the world population be in 2057?} \quad \end{align}\]

\[\begin{align} & \text{Let } P_n \text{ represent the world population n years after 2023} \quad \\[5pt] & \text{We know that } P_0 = 8 \space billion \quad \\[5pt] & \text{(a) We can formulate the recurrence relation:} \quad \\[5pt] & P_n = P_{n-1} \times 1.008 \text{ with initial condition } P_0 = 8 \space billion, n \geq 1 \mid n \in \mathbb{N} \quad \\[5pt] & \text{(b) To derive an explicit formula} \quad \\[5pt] & \text{We form a conjecture using forward substitution} \quad \\[5pt] & \text{Calculate the first few terms:} \quad \\[8pt] & ● \quad P_1 = P_0 \times 1.008 = 8b \times 1.008 \quad \\[5pt] & ● \quad P_2 = P_1 \times 1.008 = (8b \times 1.008) \times 1.008 = 8b \times (1.008)^2 \quad \\[5pt] & ● \quad P_3 = P_2 \times 1.008 = (8b \times (1.008)^n) \times 1.008 = 8b \times (1.008)^3 \quad \\[8pt] & \text{From our calculation, we form the conjecture:} \quad \\[5pt] & \qquad P_n = 8 \times (1.008)^n \quad \\[5pt] & \text{(c) Now, we calculate the population of the world in 2057:} \quad \\[5pt] & \qquad P_{2057-2023} = P_{34} = 8 \times (1.008)^{34} \approx 10.3968 \quad \\[5pt] & \text{So in 2057, the population will approximately be } 10.3968 \space billion \quad \end{align}\]

Work 21.

• Solve the following recurrence relations:

\[\begin{align} (1) \quad a_n & = 2a_{n-1} \mid n \geq 1, a_0 = 3 \quad \\[5pt] (2) \quad a_n & = 5a_{n-1} - 6a_{n-2} \mid n \geq 2, a_0 = 1, a_1 = 0 \quad \\[5pt] (3) \quad a_n & = 4a_{n-1} - 4a_{n-2} \mid n \geq 2, a_0 = 6, a_1 = 8 \quad \\[5pt] (4) \quad a_n & = -3a_{n-1} - 3a_{n-2} - a_{n-3} \mid n \geq 3, a_0 = 5, a_1 = -9, a_2 = 15 \quad \end{align}\]

• These are cases of linear homogeneous recurrence relation, we will solve accordingly:

• \((1) \quad a_n = 2a_{n-1} \mid n \geq 1, a_0 = 3\)

\[\begin{align} & \text{Given recurrence relation } a_n = 2a_{n-1} \mid n \geq 1, a_0 = 3 \quad \\[5pt] & \text{The characteristic polynomial of this recurrence relation is} \quad \\[5pt] & \qquad \quad r - 2 \quad \\[5pt] & \text{The characteristic root is r = 2. Hence, we obtain the solution:} \quad \\[5pt] & \qquad \quad a_n = A \cdot 2^n = a_0 \cdot 2^n = 3 \cdot 2^n \quad \end{align}\]

• \((2) \quad a_n = 5a_{n-1} - 6a_{n-2} \mid n \geq 2, a_0 = 1, a_1 = 0\)

\[\begin{align} & \text{Given recurrence relation } a_n = 5a_{n-1} - 6a_{n-2} \mid n \geq 2, a_0 = 1, a_1 = 0 \quad \\[5pt] & \text{The characteristic polynomial of this recurrence relation is} \quad \\[5pt] & \qquad \quad r^2 - 5r + 6 \quad \\[5pt] & \text{The characteristic root are r = 2, r = 3. Hence, we obtain the solution:} \quad \\[5pt] & \qquad \quad a_n = A \cdot 2^n + B \cdot 3^n \quad \\[5pt] & \text{Substitute n = 0} \quad \\[5pt] & \qquad \quad a_0 = A \cdot 2^0 + B \cdot 3^0 = A + B = 1 \quad (1) \quad \\[5pt] & \text{Substitute n = 1} \quad \\[5pt] & \qquad \quad a_1 = A \cdot 2^1 + B \cdot 3^1 = 2A + 3B = 0 \quad (2) \quad \\[5pt] & \text{Next, we solve system of equations (1) and (2)} \quad \\[5pt] & \quad \space (1)(2) = \begin{cases} A + B = 1 \quad \\[7pt] 2A + 3B = 0 \end{cases} \\[7pt] & \quad \space (1)(2) = \begin{cases} A = - B + 1\quad \\[7pt] 2(-B+1) + 3B = 0 \end{cases} \\[7pt] & \quad \space (1)(2) = \begin{cases} A = 3\quad \\[7pt] B = -2 \end{cases} \\[7pt] & \text{Therefore, the solution to the recurrence relation is } a_n = 3 \cdot 2^n - 2 \cdot 3^n \quad \end{align}\]

• \((3) \quad a_n = 4a_{n-1} - 4a_{n-2} \mid n \geq 2, a_0 = 6, a_1 = 8\)

\[\begin{align} & \text{Given recurrence relation } a_n = 4a_{n-1} - 4a_{n-2} \mid n \geq 2, a_0 = 6, a_1 = 8 \quad \\[5pt] & \text{The characteristic polynomial of this recurrence relation is} \quad \\[5pt] & \qquad \quad r^2 - 4r + 4 \quad \\[5pt] & \text{The characteristic root is r = 2 with multiplicity of 2.} \quad \\[5pt] & \text{Hence, we obtain the solution:} \quad \\[5pt] & \qquad \quad a_n = A \cdot 2^n + B \cdot n2^n \quad \\[5pt] & \text{Substitute n = 0} \quad \\[5pt] & \qquad \quad a_0 = A \cdot 2^0 + B \cdot 0 \cdot 2^0 = A = 6 \quad (1) \quad \\[5pt] & \text{Substitute n = 1} \quad \\[5pt] & \qquad \quad a_1 = A \cdot 2^1 + B \cdot 1 \cdot 2^1 = 2A + 2B = 8 \quad (2) \quad \\[5pt] & \qquad \quad (1)(2) \implies B = -2 \quad \\[5pt] & \text{Therefore, the solution to the recurrence relation is } a_n = 6 \cdot 2^n - 2n \cdot 2^n \quad \end{align}\]

• \((4) \quad a_n = -3a_{n-1} - 3a_{n-2} - a_{n-3} \mid n \geq 3, a_0 = 5, a_1 = -9, a_2 = 15\)

\[\begin{align} & \text{Given recurrence relation } \quad \\[5pt] & a_n = -3a_{n-1} - 3a_{n-2} - a_{n-3} \mid n \geq 3, a_0 = 5, a_1 = -9, a_2 = 15 \quad \\[5pt] & \text{The characteristic polynomial of this recurrence relation is} \quad \\[5pt] & \qquad \quad r^3 + 3r^2 + 3r + 1 \quad \\[5pt] & \text{The characteristic root is r = -1 with multiplicity of 3.} \quad \\[5pt] & \text{Hence, we obtain the solution:} \quad \\[5pt] & \qquad \quad a_n = A \cdot (-1)^n + B \cdot n(-1)^n + C \cdot n^2(-1)^n \quad \\[5pt] & \text{Substitute n = 0} \quad \\[5pt] & \qquad \quad a_0 = A \cdot (-1)^0 + B \cdot 0(-1)^0 + C \cdot 0^2(-1)^0 = A = 5 \quad (1) \quad \\[5pt] & \text{Substitute n = 1} \quad \\[5pt] & \qquad \quad a_1 = A \cdot (-1)^1 + B \cdot 1(-1)^1 + C \cdot 1^2(-1)^1 \quad \\[5pt] & \qquad \quad \quad = -A -B -C = -9 \implies B + C = 4 \quad (2) \quad \\[5pt] & \text{Substitute n = 2} \quad \\[5pt] & \qquad \quad a_2 = A \cdot (-1)^2 + B \cdot 2(-1)^2 + C \cdot 2^2(-1)^2 \quad \\[5pt] & \qquad \quad \quad = A + 2B + 4C = 15 \implies 2B + 4C = 10 \quad (3) \quad \\[5pt] & \text{Next, we solve system of equations (2) and (3)} \quad \\[5pt] & \quad \space (2)(3) = \begin{cases} B + C = 4 \quad \\[7pt] 2B + 4C = 10 \end{cases} \\[7pt] & \quad \space (2)(3) = \begin{cases} B = 4 - C \quad \\[7pt] 2(4-C) + 4C = 10 \end{cases} \\[7pt] & \quad \space (2)(3) = \begin{cases} B = 3\quad \\[7pt] C = 1 \end{cases} \\[7pt] & \text{Therefore, the solution to the recurrence relation is } \quad \\[5pt] & a_n = 5 \cdot (-1)^n + 3n \cdot (-1)^n + n^2 \cdot (-1)^n \quad \end{align}\]

Work 22.

• Solve the following recurrence relations:

\[\begin{align} & (1) \quad a_n = 3a_{n-1} + 2^n \mid n \geq 1, a_0 = 1 \quad \\[5pt] & (2) \quad a_n = 2a_{n-1} + 2n^2 \mid n \geq 2, a_1 = 5 \quad \\[5pt] & (3) \quad a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n \mid n \geq 2 \quad \\[5pt] & \small{\text{Hint: Find a particular solution of the form } qn2^n + p_1n + p_2} \quad \\[-1pt] & \small{\text{in which } q,p_1,p_2 \text{ are constants.}} \quad \end{align}\]

\[\begin{align} & a_n = a_n^h + a_n^p \quad \\[5pt] & \text{Where } a_n^h \text{ is the solution for the homogeneous part} \quad \\[5pt] & \text{And } a_n^p \text{ is the solution for the nonhomogeneous part} \quad \\[5pt] & \text{General formula: Given } F(n) = (b_tn^t + \ldots + b_0)s^n \quad \\[5pt] & \text{If s is a solution of the characteristic polynomial then:} \quad \\[5pt] & a_n^p = n^m(p_tn^t + \ldots + p_0)s^n \quad \\[5pt] & \text{Otherwise:} \quad \\[5pt] & a_n^p = n^m(p_tn^t + \ldots + p_0)s^n \quad \end{align}\]

• These are cases of linear nonhomogeneous recurrence relation, we will solve accordingly:

• \((1) \quad a_n = 3a_{n-1} + 2^n \mid n \geq 1, a_0 = 1\)

\[\begin{align} & \text{Given recurrence relation} \quad \\[5pt] & a_n = 3a_{n-1} + 2^n \mid n \geq 1, a_0 = 1 \quad \\[5pt] & \text{We define the general solution for } a_n \text{ to be } a_n = a_n^h + a_n^p \quad \\[5pt] & \text{Where } a_n^h \text{ is the homogeneous part} \quad \\[5pt] & \text{And } a_n^p \text{ is the nonhomogeneous part} \quad \\[5pt] & \text{We consider the homogeneous part:} \quad \\[5pt] & \qquad \quad a_n^h = 3a_{n-1} \quad \\[5pt] & \text{Which generates characteristic polynomial:} \quad \\[5pt] & \qquad \quad r - 3 = 0 \implies r = 3 \quad \\[5pt] & \text{We obtained solution for the homogenous part:} \quad \\[5pt] & \qquad \quad a_n^h = A \cdot 3^n \text{ with A being some constant} \quad \\[5pt] & \text{We consider the nonhomogeneous part: } F(n) = 2^n \quad \\[5pt] & \text{Try: } a_n^p = c2^n \text{ with c being some constant} \quad \\[5pt] & \text{From the given recurrence relation, we derive:} \quad \\[5pt] & \qquad \quad a_n = 3a_{n-1} + 2^n \equiv a_n - 3a_{n-1} -2^n = 0 \quad \\[5pt] & \qquad \quad \equiv c2^n -3 \cdot c2^{n-1} - 2^n = 2^n(c - \frac{3c}{2} - 1) = 0 \quad \\[5pt] & \qquad \quad \implies c = -2 \implies a_n^p = (-2) \cdot 2^n \quad \\[5pt] & \text{Thus, we have:} \quad \\[5pt] & \qquad \quad a_n = a_n^h + a_n^p = A \cdot 3^n + (-2) \cdot 2^n \quad \\[5pt] & \text{Substitute n = 0} \quad \\[5pt] & \qquad \quad a_0 = A \cdot 3^0 + (-2) \cdot 2^0 = A - 2 = 1 \implies A = 3 \quad \\[5pt] & \text{Therefore: } a_n = 3 \cdot 3^n - 2 \cdot 2^n \quad \\[5pt] \end{align}\]

• \((2) \quad a_n = 2a_{n-1} + 2n^2 \mid n \geq 2, a_1 = 5\)

\[\begin{align} & \text{Given recurrence relation} \quad \\[5pt] & a_n = 2a_{n-1} + 2n^2 \mid n \geq 2, a_1 = 5 \quad \\[5pt] & \text{We define the general solution for } a_n \text{ to be } a_n = a_n^h + a_n^p \quad \\[5pt] & \text{Where } a_n^h \text{ is the homogeneous part} \quad \\[5pt] & \text{And } a_n^p \text{ is the nonhomogeneous part} \quad \\[5pt] & \text{We consider the homogeneous part:} \quad \\[5pt] & \qquad \quad a_n^h = 2a_{n-1} \quad \\[5pt] & \text{Which generates characteristic polynomial:} \quad \\[5pt] & \qquad \quad r - 2 = 0 \implies r = 2 \quad \\[5pt] & \text{We obtained solution for the homogenous part:} \quad \\[5pt] & \qquad \quad a_n^h = A \cdot 2^n \text{ with A being some constant} \quad \\[5pt] & \text{We consider the nonhomogeneous part: } F(n) = 2n^2 \quad \\[5pt] & \text{Try: } a_n^p = cn^2+dn+e \text{ with c, d, e being some constant} \quad \\[5pt] & \text{From the given recurrence relation, we derive:} \quad \\[5pt] & \qquad \quad a_n = 2a_{n-1} + 2n^2 \equiv a_n - 2a_{n-1} - 2n^2 = 0 \quad \\[5pt] & \qquad \quad \equiv cn^2 + dn + e - 2(c(n-1)^2+d(n-1) + e) - 2n^2 = 0 \quad \\[5pt] & \qquad \quad \equiv -cn^2 -dn -e +4cn -2c +2d - 2n^2 = 0 \quad (*) \quad \\[5pt] & \text{Factor out the coefficients, we have:} \quad \\[5pt] & \qquad (*) = \begin{cases} c = -2\quad \\[5pt] -d + 4c = 0 \\[5pt] -e -2c + 2d = 0 \end{cases} \\[7pt] & \qquad (*) = \begin{cases} c = -2\quad \\[5pt] d = -8 \\[5pt] e = -12 \end{cases} \\[7pt] & \text{Thus, we have:} \quad \\[5pt] & \qquad \quad a_n = a_n^h + a_n^p = A \cdot 2^n - 2n^2 -8n - 12 \quad \\[5pt] & \text{Substitute n = 1} \quad \\[7pt] & \qquad \quad a_1 = A \cdot 2^1 - 2\cdot 1^2 -8 \cdot 1 - 12 = 5 \implies A = \frac{27}{2} \quad \\[7pt] & \text{Therefore: } a_n = \frac{27}{2} \cdot 2^n - 2n^2 -8n - 12 \quad \\[7pt] \end{align}\]

• \((3) \quad a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n \mid n \geq 2\)

\[\begin{align} & \text{Given recurrence relation} \quad \\[5pt] & a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n \mid n \geq 2 \quad \\[5pt] & \text{We define the general solution for } a_n \text{ to be } a_n = a_n^h + a_n^p \quad \\[5pt] & \text{Where } a_n^h \text{ is the homogeneous part} \quad \\[5pt] & \text{And } a_n^p \text{ is the nonhomogeneous part} \quad \\[5pt] & \text{We consider the homogeneous part:} \quad \\[5pt] & \qquad \quad a_n^h = 5a_{n-1} - 6a_{n-2} \quad \\[5pt] & \text{Which generates characteristic polynomial:} \quad \\[5pt] & \qquad \quad r^2 - 5r + 6 = 0 \text{ gives us roots: } r = 2, r = 3 \quad \\[5pt] & \text{We obtained solution for the homogenous part:} \quad \\[5pt] & \qquad \quad a_n^h = A \cdot 2^n + B \cdot 3^n \text{ with A, B being some constant} \quad \\[5pt] & \text{We consider the nonhomogeneous part: } F(n) = 2^n + 3n \quad \\[5pt] & \text{Which can be written as } F(n) = F_1(n) + F_2(n) \quad \\[5pt] & \text{Where } F_1(n) = 2^n \text{ and } F_2(n) = 3n \quad \\[5pt] & \text{Define } a_n^p = a_n^{p_1} + a_n^{p_2} \quad \\[5pt] & \text{We need to find the solution } a_n^{p_1} \text{ and } a_n^{p_2} \text{ for } F_1(n) \text{ and } F_2(n) \quad \end{align}\]

\[\begin{align} & \text{Let's find the solution for } a_n^{p_1} \quad \\[5pt] & \text{Given that } F_1(n) = 2^n \quad \\[5pt] & \text{And given 2 is a root of the characteristic polynomial} \quad \\[5pt] & \text{We try: } a_n^{p_1} = cn2^n \text{ with c being some constant} \quad \\[5pt] & \text{From the given recurrence relation, we derive:} \quad \\[5pt] & \qquad \quad a_{n_1} = 5a_{n-1} - 6a_{n-2} + 2^n \quad \\[5pt] & \qquad \quad \equiv cn2^n = 5c(n-1)2^{n-1} - 6c(n-2)2^{n-2} + 2^n = 0 \quad \\[8pt] & \qquad \quad \equiv cn2^n = \frac{5c(n-1)2^n}{2} - \frac{6c(n-2)2^n}{4} + 2^n \quad \\[8pt] & \qquad \quad \equiv cn = \frac{5c(n-1)}{2} - \frac{6c(n-2)}{4} + 1 \quad \\[8pt] & \qquad \quad \equiv cn = \frac{5cn}{2} - \frac{5c}{2} - \frac{6cn}{4} + 3c + 1 \quad \\[8pt] & \qquad \quad \equiv cn = cn + \frac{c}{2} + 1 \implies c = -2 \quad \\[8pt] & \text{Thus we have a solution } a_n^{p_1} = (-2n)2^n \quad \end{align}\]

\[\begin{align} & \text{Let's find the solution for } a_n^{p_2} \quad \\[5pt] & \text{Given that } F_2(n) = 3n \quad \\[5pt] & \text{We try: } a_n^{p_2} = dn + e \text{ with d, e being some constant} \quad \\[5pt] & \text{From the given recurrence relation, we derive:} \quad \\[5pt] & \qquad \quad a_{n_2} = 5a_{n-1} - 6a_{n-2} + 3n \quad \\[5pt] & \qquad \quad \equiv dn + e = 5(d(n-1) + e) -6(d(n-2)+e) + 3n \quad \\[5pt] & \qquad \quad \equiv dn + e = 5dn - 5d + 5e - 6dn +12d -6e +3n \quad \\[5pt] & \qquad \quad \equiv -2dn-2e+7d+3n = 0 \quad (*) \quad \\[5pt] & \text{Factor out the coefficients, we have:} \quad \\[5pt] & \qquad (*) = \begin{cases} -2d + 3 = 0 \quad \\[5pt] -2e + 7d = 0 \\[5pt] \end{cases} \\[7pt] & \qquad (*) = \begin{cases} d = \frac{3}{2} \quad \\[5pt] e = \frac{21}{4} \end{cases} \\[7pt] & \text{Thus we have a solution } a_n^{p_2} = \frac{3n}{2} + \frac{21}{4} \quad \end{align}\]

\[\begin{align} & \text{Now that we have } a_n^{p_1} \text{ and } a_n^{p_2} \text{ we have the solution:} \quad \\[5pt] & \qquad \quad a_n = a_n^h + a_n^{p_1} + a_n^{p_2} \quad \\[8pt] & \qquad \quad \quad = A \cdot 2^n + B \cdot 3^n + (-2n)2^n + \frac{3n}{2} + \frac{21}{4} \quad \\[8pt] & \text{Therefore, a solution to the given recurrence relation is:} \quad \\[5pt] & \qquad \quad a_n = A \cdot 2^n + B \cdot 3^n + (-2n)2^n + \frac{3n}{2} + \frac{21}{4} \quad \end{align}\]

Work 24.

\[\begin{align} & \text{Solve recurrence relation: } a_n = 2a_{n-1} - a_{n-2} \mid n \geq 2 \quad \\[5pt] & \text{Given } a_0 = 1, a_1 = 1 \small{\text{ (Using generating function).}} \quad \end{align}\]

\[\begin{align} & \text{We define the generating function:} \quad \\[10pt] & G_a(x) = \sum_{n=0}^{\infty} a_nx^n = \sum_{n=0}^{\infty} (2a_{n-1} - a_{n-2})x^n \quad \\[10pt] & \qquad \quad = \sum_{n=0}^{\infty} 2a_{n-1}x^n - \sum_{n=0}^{\infty} a_{n-2}x^n \quad \\[10pt] & \qquad \quad = a_0 + 2x \sum_{n=1}^{\infty} a_{n-1}x^{n-1} - \left( a_0 + a_1 + x^2 \sum_{n=2}^{\infty} a_{n-2}x^{n-2} \right) \quad \\[10pt] & G_a(x) = -1 + 2xG_a(x) - x^2G_x(x) = \frac{-1}{x^2 - 2x + 1} = \frac{-1}{(1-x)^2} \quad \\[10pt] & G_a(x) = - \sum_{n=0}^{\infty} (n+1)x^n = \sum_{n=0}^{\infty} -(n+1)x^n \quad \text{(Known sum)} \quad \\[10pt] & \text{Therefore } a_n = -n-1, n \geq 2 \mid n \in \mathbb{N} \quad \end{align}\]

• References and Extras:
  • Induction and Recursion - Hoang Anh Duc - HUS - VNU
  • UNM Department of Mathematics and Statistics - The Recurrence Relations for Janet Vassilev’s Math 327 course
  • York University - Solving Linear Recurrence Relations
  • blackpedredpen - how to solve a recurrence relation (3 ways + 1 bonus)
  • Illinois State University - Chapter 8: Recurrence Relations and Generating Functions
  • Virginia Commonwealth University - Student’s Lecture notes
  • Solving a non-homogeneous linear recurrence relation
  • Kimberly Brehm - Discrete Math II - 8.2.4 Non-Homogeneous Linear Recurrence Relations
  • TrevTutor - [Discrete Mathematics] Nonhomogeneous Recurrence Relation Examples
  • University of Hawaii System - Solving Linear Recurrence Relations
  • Use generating functions to solve recurrence relation
  • Using Generating Functions to Solve Recursively-Defined Sequences
  • Work 19. (c) Complement
  • Kenneth H. Rosen - Discrete Mathematics and Its Applications.