Define a sequence as follows:
a0 = 1
an+1 = an + 2nan2
The first few terms are 1, 2, 10, 410, 2690010, ...
Find a closed form expression for an.
The main idea is to use various substitutions to try and
reduce the complexity of the recurrence relation to
After a bit of fiddling, you may come up with the following. Let:
bn = 2n+1an
From this definition, b0 = 2, and the first few terms
are 2, 8, 80, 6560, ...
Substituting into the recurrence relation yields:
bn+1/2n+2 = bn/2n+1 + 2nbn2/22n+2
which simplifies to:
bn+1 = 2bn + bn2 = (bn + 1)2 - 1
bn+1 + 1 = ((bn + 1)2
This suggests defining:
cn = bn + 1
c0 = 3
cn+1 = cn2
The first few terms of the c sequence are 3, 9, 81, 6561, ...
which look suspiciously like powers of 3.
We conjecture that:
cn = 32n
And we can verify this since:
c0 = 320 = 31 = 3
cn+1 = 32n+1 = 32n + 2n
= 32n32n = cncn = cn2
By backwards substitution, we get the desired closed form expression:
an = (32n - 1) / 2n+1