Question

Solve the recursion relation an = 2an-1 +n, with a_o = 1.

Answer 1

$\begin{cases}a_0=1\\a_n=2a_{n-1}+n&\text{for }n>0\end{cases}$

By the definition above,

$a_{n-1}=2a_{n-2}+(n-1)$

and by substitution we get

$a_n=2(2a_{n-2}+(n-1))+n=2^2a_{n-2}+2(n-1)+n$

If we keep following this procedure, we'll start to see a pattern:

$a_{n-2}=2a_{n-3}+(n-2)$

$\implies a_n=2^2(2a_{n-3}+(n-2))+2(n-1)+n$

$\implies a_n=2^3a_{n-3}+2^2(n-2)+2(n-1)+n$

$a_{n-3}=2a_{n-4}+(n-3)$

$\implies a_n=2^3(2a_{n-4}+(n-3))+2^2(n-2)+2(n-1)+n$

$\implies a_n=2^4a_{n-4}+2^3(n-3)+2^2(n-2)+2(n-1)+n$

and so on, down to

$a_n=2^na_0+\displaystyle\sum_{i=0}^{n-1}2^i(n-i)$

Now,

$\displaystyle\sum_{i=0}^{n-1}2^i(n-i)=n\sum_{i=0}^{n-1}2^i-\sum_{i=0}^{n-1}i2^i$

One of these series is geometric and has a well-known closed form:

$\displaystyle\sum_{i=0}^{n-1}2^i=2^n-1$

The other (see note below) is a bit less obvious, but can be derived:

$\displaystyle\sum_{i=0}^{n-1}i2^i=2^n(n-2)+2$

so we have

$a_n=2^n+n(2^n-1)-(2^n(n-2)+2)$

$\implies\boxed{a_n=2^{n+1}+2^n-(n+2)}$

# # #

A brief note on how to compute the sum,

$\displaystyle\sum_{i=0}^{n-1}i2^i=2^n(n-2)+2$

The first term of the sum is 0:

$\displaystyle\sum_{i=0}^{n-1}i2^i=\sum_{i=1}^{n-1}i2^i$

Add and substract 1 to the first factor in the summand and expand the sum into two sums:

$\displaystyle\sum_{i=1}^{n-1}i2^i=\sum_{i=1}^{n-1}(i-1+1)2^i=\sum_{i=1}^{n-1}(i-1)2^i+\sum_{i=1}^{n-1}2^i$

The latter sum we're familiar with. For the other sum, we can shift the index to make it start at $i=0$, and again the first term in the sum would be 0:

$\displaystyle\sum_{i=1}^{n-1}(i-1)2^i=\sum_{i=0}^{n-2}i2^{i+1}=\sum_{i=1}^{n-2}i2^{i+1}$

So we have

$\displaystyle\sum_{i=0}^{n-1}i2^i=\sum_{i=1}^{n-2}i2^{i+1}+\sum_{i=1}^{n-2}2^i$

Continuing in this way, we would end up getting

$\displaystyle\sum_{i=0}^{n-1}i2^i=\sum_{i=1}^{n-1}2^i+\sum_{i=2}^{n-1}2^i+\sum_{i=3}^{n-1}2^i+\cdots+\sum_{i=n-2}^{n-1}2^i+\sum_{i=n-1}^{n-1}2^i$

or as a double sum,

$\displaystyle\sum_{i=0}^{n-1}i2^i=\sum_{k=1}^{n-1}\sum_{i=k}^{n-1}2^i$

which is easy to reduce:

$\displaystyle\sum_{i=k}^{n-1}2^i=2^n-2^k$

$\displaystyle\sum_{k=1}^{n-1}(2^n-2^k)=2^n(n-1)-(2^n-2)=2^n(n-2)+2$