Induction with a recursive sequence

Question

Let $(a_{n})_{n \in \mathbb N_{0}}$ be a sequence in $\mathbb Z$, defined as follows: $a_{0}:=0, a_{1}:=2, a_{n+1}:= 4(a_{n}-a_{n-1}) \forall n \in \mathbb N$.

Required to prove: $a_{n}=n2^{n} \forall n \in \mathbb N_{0}$

I have gone about it in the following:

Induction start: $n=0$ (condition fulfilled)

Induction premise: $a_{n}=n2^{n}$ for a specific $n \in \mathbb N_{0}$

Induction step:

$a_{n+1}=4(a_{n}-a_{n-1})$, and here the first problem arises, since I can say that (given the premise) $4(a_{n}-a_{n-1})=4(n2^{n}-a_{n-1})$, yet how do I get rid of the $a_{n-1}$? Surely stating the $a_{n-1}=(n-1)2^{n-1}$ is false, given that my premise is only based on an $n$ and not $n-1$.

Answer 1

Show that your premise holds for $n = 0$ and $n = 1$.

Then the induction step is: $A(n)~ ∧ ~ A(n+1) → A (n+2)$

Answer 2

Note that this can be done in an alternative way, using generating functions: $$\sum_{n=0}^{\infty} a_n x^n = 0 + 2x + 4x \sum_{n=1}^{\infty} (a_n - a_{n-1}) x^n = 2x + 4x f(x) - 4x^2 \sum_{n=0}^{\infty} a_{n} x^{n}$$

so $$f(x) = 2x+4x \left[f(x) - x f(x)\right]$$

Solving, $$f(x) = \frac{2x}{(2x-1)^2}$$

And it's easy to find the $x^n$ coefficient in this expansion.

Answer 3

We see that $$a_{n+1}-2a_n=2(a_n-2a_{n-1}),$$ which says that $b_n=a_n-2a_{n-1}$ is geometric progression.

Thus, $$b_n=b_1\cdot2^{n-1}=2\cdot2^{n-1}=2^n.$$ Thus, $$a_1-2a_0=2,$$ $$\frac{1}{2}a_2-a_1=\frac{1}{2}\cdot2^2,$$ $$\frac{1}{2^2}a_3-\frac{1}{2}a_2=\frac{1}{2^2}\cdot2^3,$$ $$.$$ $$.$$ $$.$$ $$\frac{1}{2^{n-1}}a_n-\frac{1}{2^{n-2}}a_{n-1}=\frac{2^n}{2^{n-1}},$$ which after summing sives $$\frac{1}{2^{n-1}}a_n-2a_0=2n,$$ which gives $$a_n=n2^n.$$