# Struggling with a strong induction problem involving recurrence relations

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!

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.

• So to avoid that - and I suppose this is the point of strong induction - I should prove the base case for $b_1$, because otherwise the proof would be nonsensical, right? Commented Dec 18, 2016 at 19:51
• @mvw: Yes, I should have probably written "for all $k\leq n$" in the second phase (and then use $k$ instead of $n$). In other words, write this proof as strong induction (not just as induction)... Commented Dec 18, 2016 at 20:16
• @AustinMohr: Rephrased it a bit. Commented Dec 18, 2016 at 20:30
• @mvw: Rephrased it a bit. Commented Dec 18, 2016 at 20:30
• @ChrisT: Rephrased it a bit. Commented Dec 18, 2016 at 20:30

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.

• Forgive me for being obtuse and asking so many questions (I feel comfortable with induction but problems like this, using strong induction and recurrences, throw me for a loop somewhat)!. So I establish base cases for $5\:\cdot \:3^n\:+\:7\:\cdot \:2^n$, and then prove it inductively from n = 2? Do I at any point show that $5\:\cdot \:3^n\:+\:7\:\cdot \:2^n$ is equivalent to the given recurrence relation, or do I not have to do that? Commented Dec 18, 2016 at 19:18
• The induction is for the relation, and the base case of that induction is $n=2$. Strong induction will proof the relation for all $n$ with $n\ge 2$. The proof of $n=2$ will need that the initial conditions $b_0=12$ and $b_1=29$ hold for the closed form, thus instances $n=0$ and $n=1$.
– mvw
Commented Dec 18, 2016 at 19:20
• I think I get it now. $P_(k+1)$ should equal $5\:\cdot \:3^(k+1)\:+\:7\:\cdot \:2^(k+1)$ . I should then be able to get $5b_{k}-6b_{k-1}$ from that algebraically, right? Commented Dec 18, 2016 at 19:30