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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

$$\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}$$

Block

$$\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}$$

Block

$$\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}$$

Block

• 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}$$

Block

$$\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}$$

Block

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}$$

Block

• 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}$$

Block

• $(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}$$

Block

• $(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}$$

Block

• $(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}$$

Block