General form of $a_n$ given $ a_n=2a_{n-1}+2^{n-1} $, $a_2=4$, $a_3=12$

Question

I know the answer is $a_n=n2^{n-1}$, can someone give me an idea of the approach? Actually $a_n$ is the number of edges of a n-cube.

Answer 1

We have $$a_n = 2a_{n-1} +2^{n-1} $$ and similarly we get, $$a_{n-1} =2a_{n-2}+2^{n-2} $$ and soon. Thus, we can write $$a_n = 2 [2a_{n-2} +2^{n-2}]+2^{n-1} $$ $$= 8a_{n-3} + 2^{n-1}\times 3$$ and so on. We can thus generalise this result to $$a_n =2^ka_{n-k} +k2^{n-1} $$ Substituting $k= n-1$ and using $a_1 =1$, we can easily get $$a_n =n\cdot 2^{n-1} $$ Hope it helps.

Answer 2

We must assume $a_1=1$. After this it is easy with induction.

Clearly it hold when $a_1=1$.

For the inductive step notice $a_{n+1}=2a_n+2^{n}=2(n2^{n-1})+2^n=n2^n+2^n=(n+1)2^n$ as desired.

Answer 3

Let $a_m=b_m+(am+b)2^m$

$$2^{n-1}=a_n-2a_{n-1}=b_n+(an+b)2^n-2\{b_{n-1}+(a\overline{n-1}+b)2^{n-1}\}$$

$$\implies2^{n-1}=b_n-2b_{n-1}+2^{n-1}(2a)$$

Choose $2a=1, b=0$ so that $b_n-2b_{n-1}=0\iff b_n=2b_{n-1}$

$4=a_2=b_2+b2^2\iff b_2=-4b=0$

$12=a_3=b_3+\left(\dfrac32+b\right)2^3\iff b_3=-8b=0$

$\implies b_n=0\forall n>1$