A Growing Sequence

Solution

The main idea is to use various substitutions to try and reduce the complexity of the recurrence relation to something manageable.

After a bit of fiddling, you may come up with the following. Let:

b_n = 2ⁿ⁺¹a_n

From this definition, b₀ = 2, and the first few terms are 2, 8, 80, 6560, ...

Substituting into the recurrence relation yields:

b_n+1/2ⁿ⁺² = b_n/2ⁿ⁺¹ + 2ⁿb_n²/2²ⁿ⁺²

which simplifies to:

b_n+1 = 2b_n + b_n² = (b_n + 1)² - 1

Hence:

b_n+1 + 1 = ((b_n + 1)²

This suggests defining:

c_n = b_n + 1

yielding:

c₀ = 3
c_n+1 = c_n²

The first few terms of the c sequence are 3, 9, 81, 6561, ... which look suspiciously like powers of 3. We conjecture that:

c_n = 3²ⁿ

And we can verify this since:

c₀ = 3²⁰ = 3¹ = 3
c_n+1 = 3²ⁿ⁺¹ = 3^{2n + 2n} = 3²ⁿ3²ⁿ = c_nc_n = c_n²

By backwards substitution, we get the desired closed form expression:

a_n = (3²ⁿ - 1) / 2ⁿ⁺¹