Consider the following sequence:

Question

$a_j = 4a_{j-1} - 4a_{j-2}$

$a_0=0;\ a_1 = 1$

For all $j\geqslant2$, come up with a general formula for the term $a_j$. Use mathematical induction to prove your claim.

I have calculated the first few terms of this sequence, and determined from them that $a_j = j · 2^{j-1}$.

However, I am very bad at induction (some might even say weak at it) and would appreciate if someone could help me prove that this is in fact the case.

Answer 1

In your case, since your linear recurrence relation uses $2$ smaller subscripts in the definition for $a_j$, you want to use strong induction to prove that

$$a_j = j\left(2^{j-1}\right), \; j \ge 0 \tag{1}\label{eq1A}$$

In this situation, you need to verify $2$ base cases. Although the question asks you prove \eqref{eq1A} holds for $j \ge 2$, it actually holds starting at $0$. As such, you can start there to first verify it works for $j = 0$ and $j = 1$. This is true since $0 = 0(2^{-1})$ and $1 = 1(2^{0})$, respectively.

Next, assume for some $k \ge 1$ that \eqref{eq1A} holds for all $j \le k$. For $j = k + 1$, you have

$$\begin{equation}\begin{aligned} a_{k + 1} & = 4a_{k} - 4a_{k - 1} \\ & = 4k\left(2^{k-1}\right) - 4(k-1)\left(2^{k-2}\right) \\ & = 2k\left(2^{k}\right) - (k-1)\left(2^{k}\right) \\ & = 2^{k}(2k - (k - 1)) \\ & = (k+1)2^{k} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

This shows \eqref{eq1A} also holds for $j = k + 1$. Thus, by strong induction, \eqref{eq1A} holds for all $j \ge 0$.

Answer 2

For $$A_j=4(A_{i-1}+A_{j-2}),$$ let $A_j=x^j$ to get $x^2-4x+4=0 \implies x=2,2$ (repeated roots). So the general solution of $A_j$ is given as $$A_j=(aj+b)x^j=(aj+b)2^j$$ Using the given initial values we get $a=1/2,b=0$ Finally $A_j=j2^{j-1}$

Answer 3

Note that $a_n-2a_{n-1}=2(a_{n-1}-2a_{n-2})$ and therefore by introducing a new sequence $b_n=a_n-2a_{n-1}$ you can obtain $b_n=2b_{n-1}$ and $b_1=1.$ This is exactly the geometric progression with first term $1$ and common ratio $2.$ Hence $b_n=2^{n-1}$ for all $n\in\mathbb{N}.$

Now, observe that $$a_n=(a_n-2a_{n-1})+2(a_{n-1}-2a_{n-2})+2^2(a_{n-2}-2a_{n-3})+\cdots+2^{n-1}(a_1-2a_0)$$ and, as we found this is equal to $$2^{n-1}+2.2^{n-2}+2^2.2^{n-3}+\cdots+2^{n-1}.2^0=n.2^{n-1}$$ for all $n\in\mathbb{N}.$