# Recursively Define & Prove Through Strong Induction

hopefully you guys will be able to help me.

I need to recursively define $a_n = 6a_{n-1}-9a_{n-2}$, and prove $a_n=(5-n)\cdot3^n$ $a_0 = 5$ and $a_1 = 12$

I've already done the basis case for this induction problem, but I am stuck on the second induction step. I know the following though:

$a_k(rec)=a_k(exp)$, for all $i = 0,1,2,3,\ldots,k$.

Prove $a_{k+1}(rec)=a_{k+1}(exp)$

asub(k+1) = (5-(k+1))3^(k+1) = 6(5-k)3^k - 9(5-(k+1)3^(k-1)

I don't even know if I did this correct, but this problem seems a lot harder than the other recursion problems that I have done.

• What means asub, rec, exp? – Masacroso Nov 30 '15 at 4:26
• recursive and expected – daniel death Nov 30 '15 at 4:27
• Still I dont understand. Recursive and expected, by themselves, doesnt mean something on math. I assume you are using some kind of informatic language. – Masacroso Nov 30 '15 at 4:28
• Rec is the original definition with asub(n) = 6asub(n-1)-9asub(n-2) Exp is what I am trying to prove with asub(n)=(5-n)*3^n I guess it kind of isn't required, that's just how I was taught. – daniel death Nov 30 '15 at 4:32
• Maybe you are on the way. In principle you are using strong induction. In the notation you are using, you want to prove that $6(5-k)3^k -9(5-(k-1))3^{k-1}=(5-(k+1))3^{k+1}$. Note that you had it slightly wrong. – André Nicolas Nov 30 '15 at 4:36

$a_{k+1} = 6a_k - 9a_{k-1}$ because of the recursive definition.
Your assumption gives you formulas for $a_k$ and $a_{k-1}$ but not for $a_{k+1}$. However, you can substitute these formulas, to get $a_{k+1} = 6(5-k)\cdot 3^k - 9\cdot (5-(k-1))\cdot 3^{k-1}$. (This is what I think is meant by $rec$).
Now do some algebra and make the right-hand side look like $(5-(k+1))\cdot3^{k+1}$, (which is what I think you mean by $exp$).
$$a_n-3a_{n-1}=3(a_{n-1}-3a_{n-2})=\cdots=3^{n-1}(a_1-3a_0)$$ $$a_n-3a_{n-1}=3^{n-1}(a_1-3a_0)$$ $$3a_{n-1}-3^2a_{n-2}=3\cdot3^{n-2}(a_1-3a_0)$$ $$\cdots$$ $$3^{n-1}a_1-3^na_0=3^{n-1}\cdot3^0(a_1-3a_0)$$ Adding side by side, $$a_n-3^na_0=n\cdot3^{n-1}(a_1-3a_0)$$ $$a_n=n\cdot3^{n-1}a_1-(n-1)\cdot3^na_0$$