Solution to the recurrence $a_n = 2a_{n - 1} - 2^n$

Question

I came across the following recurrence in a blackpenredpen video while learning about generating functions:

$$ a_n = 2 a_{n - 1} - 2^n $$

with $a_0 = 5$. Before attempting to solve it using generating functions I solved it by expanding out the first few terms:

$$ a_n = 2^2 a_{n - 2} - 2 \cdot 2^n $$ $$ a_n = 2^3 a_{n - 3} - 3 \cdot 2^n $$ $$ a_n = 2^4 a_{n - 4} - 4 \cdot 2^n $$

and after a few more terms we deduce $a_n = 5 \cdot 2^n - n 2^n = (5 - n) 2^n$ which we verify using induction. There was some luck in arriving at this form, since it involved some guesswork.

How can this recurrence be solved using generating functions? Of course other methods for solving the recurrence will also be appreciated :).

Answer 1

The recurrence can be solved using generating functions. We have the recurrence:

$$ a_n = 2 a_{n - 1} - 2^n $$

Summing all $a_n$ and converting to power series we get, according to the recurrence relation:

$$ \sum_{n = 1}^{\infty} a_n x^n = 2 \sum_{n = 0}^{\infty} a_n x^{n + 1} - \sum_{n = 1}^{\infty} 2^n x^n$$ $$ \sum_{n = 1}^{\infty} a_n x^n = 2 x \sum_{n = 0}^{\infty} a_n x^n - \sum_{n = 1}^{\infty} 2^n x^n$$

We now define $A(x) = \sum_{n = 0}^{\infty} a_n x^n$. Plugging into above we get:

$$ A(x) - a_0 = 2x A(x) - \sum_{n = 1}^{\infty} 2^n x^n$$

Now using the fact that $x$ is arbitrary and we are only interested in the coefficients of the series, which are the elements of the recurrence relation, we may choose $x$ such that $\sum_{n = 1}^{\infty} 2^n x^n$ converges, getting:

$$ A(x) - a_0 = 2x A(x) - \left( \frac{1}{1 - 2x} - 1 \right) $$

Rearranging we get:

$$ A(x) = \frac{a_0 - 2a_0 x - 2x}{\left( 1 - 2x \right)^2} = \frac{5 - 12x}{\left( 1 - 2x \right)^2} $$

Applying partial fraction decomposition to the above gives us:

$$ A(x) = \frac{6}{1 - 2x} - \frac{1}{\left(1 - 2x \right)^2}$$

Now we need to convert above to a power series to obtain the coefficients which are the elements of the recurrence. We have that:

$$ \frac{1}{1 - 2x} = \sum_{n = 0}^{\infty} 2^n x^n $$

Therefore:

$$ A(x) = 6\sum_{n = 0}^{\infty} 2^n x^n - \frac{1}{\left(1 - 2x \right)^2}$$

We can deduce the series for $\frac{1}{\left(1 - 2x \right)^2}$ by differentiating $\frac{1}{1 - 2x}$:

$$ \frac{2}{\left( 1 - 2x \right)^2} = \frac{d}{dx} \frac{1}{1 - 2x} = \sum_{n = 1}^{\infty} 2^n \cdot n x^{n - 1}$$

From which we conclude that:

$$ A(x) = 6\sum_{n = 0}^{\infty} 2^n x^n - \sum_{n = 1}^{\infty} 2^{n - 1} \cdot n x^{n - 1}$$

Or:

$$ A(x) = 6\sum_{n = 0}^{\infty} 2^n x^n - \sum_{n = 0}^{\infty} (n + 1) 2^n x^n$$ $$ A(x) = \sum_{n = 0}^{\infty} (5 - n) 2^n x^n $$

Which means $a_n = (5 - n)2^n$.

Answer 2

Here are the main basic methods to tackle such a recurrence relation.

1. Guessing

You can guess/propose a solution after computing a few steps. That's what you did.

2. Ansatz

As this recurrence relation is inhomogeneous and linear, the general solution $a_n = b_n + c_n$ will be made up of the general solution to the associated homogeneous problem, i.e. $b_n = 2b_{n-1}$, and a particular solution $c_n$ to the original inhomogeneous recurrence relation.

The homogeneous problem shows constant coefficients, that is why it can be handled straighforwardly thanks to its characteristic polynomial, i.e. $r = 2$ in the present case, such that $b_n = 2^n\alpha$, with $\alpha$ a constant.

The particular solution to $c_n = 2c_{n-1} - 2^n$ will be here "guessed" too by invoking an ansatz. But which ansatz to choose ? Actually, there is not much than intuition in order to do so, which is developped through training. Usually the structure of the particular solution $c_n$ ressembles the inhomogeneous term, so that we can propose $c_n = 2^n\beta$ and plug it into the equation in order to determine the parameter $\beta$.

However, since the base of the exponential $2^n$ coincides with the root $r = 2$ of the characteristic polynomial, we will end up with the same solution as $b_n$, that is why we need another ansatz. The usual trick thus adds a polynomial prefactor, such that $c_n = 2^n(\beta n + \gamma)$, hence $c_n - 2c_{n-1} + 2^n = 2^n(\beta+1) = 0$, which leads to $\beta = -1$ and in the end $c_n = -2^nn$.

Collecting up all the elements finally, we find $a_n = b_n + c_n = 2^n(\alpha-n)$, with $\alpha = 5$ due to the initial condition $a_0 = 5$.

3. Systematic resolution

How to find a solution without guessing/ansatz ? See this other answer of mine.

4. Generating function

Cf. prcssngnr's great answer.

Answer 3

A much simpler path to the solution can found found transforming the sequence to a more common Fibonacci-type form, (e.g., $f_n=af_{n-1}+bf_{n-1}$) for which solutions are already known. To that end, consider

$$\frac{a_{n}-2a_{n-1}}{a_{n-1}-2a_{n-2}}=\frac{-2^n}{-2^{n-1}}=2$$

Then, with some rearrangement of terms we achieve the desired equation, namely

$$a_n=4a_{n-1}-4a_{n-2}$$

with $a_0=5$ as given, and $a_1=2a_0-2=8$.

I have commented frequently on the solution to these types of equations, giving detailed analytic solutions. See, for example, Generalized Fibonacci Sequence. In the present case, the solution will simplify to the same result as given by @prcssngnr, namely

$$a_n=(na_1-(n-1)2a_0)2^{n-1}=(5-n)2^n$$

I have verified these results numerically.