Struggling with a strong induction problem involving recurrence relations

Question

The problem states:

Let $b_0$ = $12$ and $b_1$ = $29$, and for all integers $k ≥ 2$, let $b_k$ = $5b_{k-1}-6b_{k-2}$.

Prove that for all $n ≥ 0$, $b_n$ = $5\:\cdot \:3^n\:+\:7\:\cdot\:2^n$

I'm familiar with questions where I'm supposed to find the close form of a recurrence relation, and then prove that formula via induction. This question is more strangely structured, however, and I'm not sure how to proceed. Am I supposed to show that:

$b_k$ = $5b_{k-1}-6b_{k-2}$ = $b_n$ = $5\:\cdot \:3^n\:+\:7\:\cdot \:2^n$

i.e. use strong induction to show both statements are equivalent?

If that's the case, do I show $b_n$ = $5\:\cdot \:3^n\:+\:7\:\cdot \:2^n$ holds for n = 0 and 1 (establishing base cases) and then manipulate what emerges algebraically to equal $b_k$ = $5b_{k-1}-6b_{k-2}$ ? Or should I do that to $b_k$ = $5b_{k-1}-6b_{k-2}$? Advice and insight is most welcome!

Answer 1

First, show that this is true for $n=0$ and $n=1$:

$b_{0}=5\cdot3^{0}+7\cdot2^{0}$

$b_{1}=5\cdot3^{1}+7\cdot2^{1}$

Second, assume that this is true for $n-2$ and $n-1$:

$b_{n-2}=5\cdot3^{n-2}+7\cdot2^{n-2}$

$b_{n-1}=5\cdot3^{n-1}+7\cdot2^{n-1}$

Third, prove that this is true for $n$:

$b_{n}=$

$5\color\red{b_{n-1}}-6\color\green{b_{n-2}}=$

$5(\color\red{5\cdot3^{n-1}+7\cdot2^{n-1}})-6(\color\green{5\cdot3^{n-2}+7\cdot2^{n-2}})=$

$25\cdot3^{n-1}+35\cdot2^{n-1}-30\cdot3^{n-2}-42\cdot2^{n-2}=$

$25\cdot3^{n-1}+35\cdot2^{n-1}-10\cdot3^{n-1}-21\cdot2^{n-1}=$

$15\cdot3^{n-1}+14\cdot2^{n-1}=$

$5\cdot3^{n}+7\cdot2^{n}$

---

Please note that the assumption is used only in the parts marked red and green.

Answer 2

I think you just have to show that $b_n = 5\cdot 3^n + 7\cdot 2^n$ fulfills the recurrence relation and initial conditions for every instance $n$. As the relation involves up to two prior sequence elements I would use strong induction.

You start with direct proofs for $b_0$, then $b_1$ and the induction from $n=2$.

Update: It seems I need to provide a full solution:

The initial conditions hold by evaluation and comparison. $$ S(0): b_0 = 12 \wedge b_0 = 5\cdot 3^0 + 7\cdot 2^0 = 5 + 7 = 12 \\ S(1): b_1 = 29 \wedge b_1 = 5\cdot 3^1 + 7\cdot 2^1 = 15 + 14 = 29 \\ $$ Where the $\wedge$ means logical "and".

The statement for $n$, $n\ge 2$ is $$ S(n): b_n = 5 b_{n-1} - 6 b_{n-2} \wedge b_n = 5\cdot 3^n + 7\cdot 2^n $$ Base case $n=2$: $$ S(2):b_2 = 5 b_1 - 6 b_0 \wedge b_2 = 5 \cdot 3^2 + 7 \cdot 2^2 $$ This evaluates to $$ S(2): b_2 = 5 \cdot 29 - 6 \cdot 12 = 145-72=73 \wedge b_2 = 45 + 28 = 73 $$ which is a true statement.

Induction Step:

Assuming $S(k)$ is true for $k\in\{2,\dotsc, n\}, n\ge 2$ we have $$ S(k+1): b_{k+1} = 5 b_k - 6 b_{k-1} \wedge b_{k+1} = 5\cdot 3^{k+1} + 7\cdot 2^{k+1} $$ where \begin{align} b_{k+1} &= 5 b_k - 6 b_{k-1} \\ &= 5 \left( 5\cdot 3^k + 7\cdot 2^k \right) - 6 \left( 5\cdot 3^{k-1} + 7\cdot 2^{k-1} \right) \end{align} The first term in parentheses is justified by the truth of $S(k)$. The second term needs a case distinction: For $k=2$ it relies on the truth of the fulfillment of the base condition $b_1$, otherwise we can build on the true statements $S(k-1)$. Then: $$ \begin{align} b_{k+1} &= (25 - 10) 3^k + (35-21) 2^k \\ &= 15\cdot 3^k + 14\cdot 2^k \\ &= 5\cdot 3^{k+1} + 7\cdot 2^{k+1} \end{align} $$ so we end up with $$ S(k+1): b_{k+1} = 5\cdot 3^{k+1} + 7\cdot 2^{k+1} \wedge b_{k+1} = 5\cdot 3^{k+1} + 7\cdot 2^{k+1} $$ which is a true statement.

By the principle of strong induction we conclude the truth of $S(n)$ for all integer $n$ with $n>=2$.

Adding the truth of the initial conditions we can claim the truth of $S(n)$ for all integer $n$ with $n \ge 0$.

Now \begin{align} S(0)&: b_0 = 12 \wedge b_0 = 5\cdot 3^0 + 7\cdot 2^0 \\ S(1)&: b_1 = 29 \wedge b_1 = 5\cdot 3^1 + 7\cdot 2^1 \\ S(n)&: b_n = 5 b_{n-1} - 6 b_{n-2} \wedge b_n = 5\cdot 3^n + 7\cdot 2^n \quad (n \ge 2) \end{align} means that for all integer $n$ with $n\ge 0$ the sequence $b_n = 5\cdot 3^n + 7\cdot 2^n$ is the solution of the recurrence relation.