[Math] solve recurrence relation using mathematical induction

discrete mathematicsinduction

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$

Best Answer

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.

Related Question