# solve recurrence relation using mathematical induction?

solve recurrence relation $a_n = 6 a_{n–1} – 9 a_{n–2}$, where $a_0 = 1$ and $a_1 = 6$ and Verify, using Principle of Mathematical Induction, that $a_n = 3^n + n 3^n$.

ans: i have done so far...
put $a_n=b_n$
$a_n-6a_{n-1}+9a_{n-2}=0$
$b_n-6b_{n-2}+9a_{n-2}=0$
$b^2-6b+9=0$, $b=3,3$

general solution: $a_n=(c_1+c_2n)3^n$

• Please check to be sure that I guessed right in interpreting your formulas and in supplying the missing value for $a_0$. – Brian M. Scott Sep 13 '13 at 7:56
• I fail to understand the "ans" paragraph. Aren't you asked to use mathematical induction? (Presumably, on $n$... So, the beginning of the proof should read something like "Let $n=0$. The property holds because... Then...") – Did Sep 13 '13 at 7:57
• @Did: He appears to have been asked both to solve and to verify, the latter using math. ind. – Brian M. Scott Sep 13 '13 at 7:58
• @BrianM.Scott I've altered some of your edit $a_0=1$ and $3^n$ rather than $3n$ – Mark Bennet Sep 13 '13 at 7:58
• @Mark: You’re right. (And you and I were editing the $0$ into $1$ simultaneously after you corrected the $3n$.) – Brian M. Scott Sep 13 '13 at 7:59

It makes no sense to ‘put $a_n=b_n$’ when you have no $b_n$ in the problem. What you wanted is the auxiliary equation $b^2-6b+9=0$, which you correctly solved to find the general solution

$$a_n=(c_1+c_2n)3^n\tag{1}$$

for some constants $c_1$ and $c_2$. You determine those by using the known values of $a_0$ and $a_1$: when $n=0$ equation $(1)$ becomes

$$1=a_0=(c_0+c_2\cdot0)\cdot3^0\;,\tag{2}$$

and when $n=1$ it becomes

$$6=a_1=(c_1+c_2\cdot1)\cdot3^1\;.\tag{3}$$

Now simplify $(2)$ and $(3)$ and solve for $c_1$ and $c_2$ to finish deriving the solution.

To verify it by mathematical induction you must do three things:

1. verify that $3^0+0\cdot3^0=a_0$, i.e., that the formula gives the correct value when $n=0$;
2. verify that $3^1+1\cdot3^1=a_1$, i.e., that the formula gives the correct value when $n=0$; and
3. show that if $n\ge 2$ and $a_k=3^k+k3^k$ for $k=0,1,\ldots,n-1$, then $a_n=3^n+n3^n$.

(1) and (2) are the basis steps of your induction, and (3) is the induction step: in it you’re showing that if the expression $3^k+k3^k$ gives the right value for $a_k$ for all $k<n$, then it also gives the correct value for $a_n$. In carrying out this step you’ll use the recurrence that defines the sequence.

If $n=0$ then $a_{0}=1$ and $3^{0}+0=1$ so the formula agrees here.

$a_{1}=6$ by definition and $3^{1}+1\cdot3^{1}=6$ so it is true for $n=1$. Assume this is true for all $k\le n$. We now show this for $n+1$.

$a_{n+1}=6a_{n}-9a_{n-1}=6\big(3^{n}+n3^{n}\big)-9\big(3^{n-1}+(n-1)3^{n-1}\big)$

$=6\cdot3^{n}+6n\cdot3^{n}-9\cdot3^{n-1}-9(n-1)3^{n-1}=2\cdot3^{n+1}+2n\cdot3^{n+1}-3^{n+1}-(n-1)\cdot 3^{n+1}=3^{n+1}+(n+1)\cdot3^{n+1}$.