# Solve the recurrence and verify the formula using strong induction

Let $a_n$ defined recursively by $a_0$ = 2, $a_1 = 4$ and

$a_{n+1}$ = 4$a_n$ - 3$a_{n-1}$, n $\ge$ 1

Solve the recurrence relation and verify the formula by using strong induction.

Attempt (not sure if it's right):

$\Rightarrow a_{n+1} - 4a_n + 3a_{n-1} = 0 \Rightarrow a^{n+1} - 4a^n + 3a^{n-1}$ = 0

$\Rightarrow a^2 - 4a + 3 = 0 \Rightarrow (a - 3)(a - 1) = 0 \Rightarrow a$ = 3,1

$\Rightarrow a_0 = 2 = B(3^n) + C = B + C$ = 2

$\Rightarrow a_1 = 4 = B(3^n) + C = 3B + C = 4$ $\Rightarrow B = 1, C = 1$

$\Rightarrow$ General formula: $a_n = 3^n + 1^n$

Hypothesis would be $n > 1$ and $a_k \ge K$ for integers K such that $1 \le K < n$ ?

Not sure what to do next or if I was right up to this point

Edit (added another question)

$a_n = 5a_{n-1} - 6a_{n-2}, r_0=0$ and $r_1=1$

General formula $a_n= 3^n - 2^n$

Let us assume for some $n \ge 0, a_{n-1} = 3^{n-1} - 2^{n-1}$ and $a_{n-2} = 3^{n-2} - 2^{n-2}$ Is this the right hypothesis?

Thanks

• The general formula is correct. First show it for $n=1$ and $n=2$. Then, show that the formula is correct for $a_{n+2}$, if it is correct for $a_{n+1}$ and $a_n$ – Peter Dec 19 '16 at 15:18
• Can I check for $a_{n-1}$, $a_{n-2}$, and prove $a_{n+1}$ ? Like in the hypothesis above? Not sure if it makes any difference. – itproxti Dec 19 '16 at 17:09
• Not quite, you have to ASSUME that the claim holds for $a_{n-2}$ and $a_{n-1}$ and to prove it for $a_n$. The base case consists of showing the claim for $n=1$ and $n=2$ – Peter Dec 19 '16 at 17:09
• Why prove $a_n$? if I prove $a_{n+1}$ then I have proved $a_n$ as well, no? btw, is my hypothesis above correct? :) – itproxti Dec 19 '16 at 17:14
• Ok, I get it now. Thank you and all best to you Peter! – itproxti Dec 19 '16 at 17:52

## 1 Answer

Your approach is right, you did find the series. However, your redaction and reasoning are both terrible.

What you just wrote should not be on an answer. It is a draft that enables you to get the formula.

Once you have it, you can write the following.

$a_0=3^0+1$ and $a_1=3^1+1$. Let us assume that for some $n\geq 1$, $a_n=3^n+1$ and $a_{n-1}=3^{n-1}+1$. Let us calculate $a_{n+1}$

$a_{n+1} = 4(3^n+1)-3(3^{n-1}+1)=3^{n+1}+1$ (What a surprise! I didn't expect this at all...)

So by induction, $\forall n \in \mathbb{N}, a_n=3^n+1$

This kind of reasoning can be disturbing at first. But it is one valid way to proove your result. The disturbing fact is that the formula looks like it comes out of nowhere, you just tried formulas all day long and found one that fits. It is correct redaction, though.

Your implications do not prove anything. The first one (where you go from $a_n$ to $a^n$ somehow) is wrong, unless you assume some specific form for $a_n$ (and in this case you should change your notations).

Even if you had only valid implications to some property $A$, it would only show that any such sequence must verify property $A$, not that all sequences that verify property $A$ are solutions to your problem.

• Thank you for your help and criticism. I should have added $a_n=r_n(a!=0)$ and went from there, sufficient? For the strong induction I still don't quite grasp it. I have posted(edited) another question, please have a look at it. Thank! – itproxti Dec 19 '16 at 17:09
• Vincent do you have proof that the reasoning is wrong?I'm 95% sure that the reasoning here is sound.The wikipedia agrees that this is the way to solve this kind of reccurence relations en.wikipedia.org/wiki/… – kingW3 Dec 19 '16 at 17:13
• It is the way to solve it, but not the way to prove that this is a solution. – Vincent Dec 19 '16 at 17:20