2
$\begingroup$

Let $a_0 = 0, a_1 = 1$, and let $a_{n+2} = 6a_{n+1} - 9a_n$ for $n\geq 0.$ Prove $a_n = n 3^{n-1}$ for $n\geq 0.$

attempt: Suppose $a_0 = 0, a_1 = 1$, and let $a_{n+2} = 6a_{n+1} - 9a_n$. Then notice when $n = 0$, we have $a_2 = 6_{1} - 9a_0 = 6-0 = 6$. And $a_2 = 2*(3^{2-1}) = 6.$ Suppose as inductive hypothesis this is true for all $n \geq 0.$ Then we need to show $a_{n+1} = (n+1) 3^{(n+1)-1}= (n+1)*3^n$.

Then $a_{n+1} = 6a_{n}-9a_{n-1}$ by the recurrence relation. So $a_{n+1} = 6a_{n}-9a_{n-1} = 6(n 3^{n-1})- 9a_{n-1} = 3[2(n 3^{n-1})] - 3a_{n-1}]= $ I am stuck after this, I want to show $a_{n+1} = (n+1)*3^n$.

Can someone please help ? Thank you

$\endgroup$
3
$\begingroup$

Induction.

True for $n=0,n=1$. We will assume true up to $n$, will show holds for $n+1$: $$a_{n+1} = 6 a_n -9 a_{n-1} = 6 n 3^{n-1} - 9 (n-1) 3^{n-2}=(2n -(n-1))3^n=(n+1)3^{(n+1)-1}.$$

$\endgroup$
0
$\begingroup$

First off let us see if the base case holds. $a_{0}$=$0*3^n-1$=0 that means $a_{0}$ holds $a_{1}$=$1*3^0=1$ that means $a_{1}$ holds too

Then to do the inductive step we have to see if n+1 holds.

$a_{n+3}$=$6(n+2)*3^n$ + $2$ - $1$ - $9(n+1)*3^n$ =$2(n+2)*3^n+2$-$(n+1)*3^n+2$=$3^n+2(2(n+2)-n+1)$= $3^{n+2}(n+3)$

That means that the inductive step holds, since if we subsitiute n+3 into our formula we get $a_{n+3}$ =$3^{n+2}(n+3)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.