Prove a recursive sequence using induction

Question

I'm having trouble with this recursive sequence question and was wondering how to prove it.

The sequence $a_n$ is defined recursively by, $a_1 = 6$, $a_2 = 8$, $a_n = 4(a_{n-1}) - 4(a_{n-2})$ for $n>2$.

Prove that $a_n = (4-n)(2^n)$ for all $n$ in the naturals.

So far I have done the base case for $n=1$ and $n=2$ which hold true and assume it is true for $n = 1$, $2$, $3$, ..., $k$

$$a_k = (4-k)(2^k)$$ $$a_{k+1} = (4-(k+1))(2^{k+1})$$ Then I use the given sequence. $$a_{k+1} = 4(a_k)-4(a_{k-1})$$ $$= 4(4-k)(2^k)-4(4-(k-1))(2^{k-1})$$ Using the Induction hypothesis: $$= 2^{k+2}(4-k)-(3-k)(2^{k+1})$$ This is where I get stuck, only the part after the subtraction sign is what I want but I have the extra piece before it. Any help is appreciated.

Answer 1

Here is my answer:

Base cases: $a_1 = (4 - 1) 2^1 = 6$ and $a_2 = (4 - 2) 2^2 = 8$.

Let $a_k = (4 - k) 2^k$ be true for any integer $k > 2$.

Now, $a_{k+1} = 4 (a_k - a_{k-1}) $

Substitute $a_k = (4-k)2^k$ and $a_{k-1} = (4-(k-1))2^{k-1}$.

$\therefore a_{k+1} = 4[(4-k)2^k - (4 - (k-1))2^{k-1}] $

$\therefore a_{k+1} = 4 \times 2^{k-1} [8 - 2k - (5 - k)] $

$\therefore a_{k+1} = 2^{k+1} [3 - k]$

Adding and subtracting 1 in the bracket, we have:

$a_{k+1} = (4 - (k+1)) 2^{k+1}$, as required.

Answer 2

Alt. hint (without induction): $\;a_n = 4a_{n-1} - 4a_{n-2} \iff a_n - 2 a_{n-1}=2(a_{n-1}-2a_{n-2})\,$, therefore $\,a_n - 2 a_{n-1}\,$ is a geometric progression with common ration $\,2\,$ and:

$$ a_n - 2 a_{n-1}=2(a_{n-1}-2a_{n-2}) = 2^2(a_{n-2}-2a_{n-3})=\ldots=2^{n-2}(a_2-2a_1)=-2^n $$

Then $\,a_n - 2 a_{n-1}=-2^n \iff \dfrac{a_n}{2^n}-\dfrac{a_{n-1}}{2^{n-1}}=-1\,$, therefore $\,\dfrac{a_n}{2^n}\,$ is an arithmetic progression with common difference $\,-1\,$ and:

$$ \dfrac{a_n}{2^n}=\dfrac{a_{n-1}}{2^{n-1}}-1=\dfrac{a_{n-2}}{2^{n-2}}-2=\ldots = \dfrac{a_1}{2}-(n-1)=4-n $$