From the given recurrence, it follows that
and so on down to the first term,
(Notice how the exponent on the 2 and the subscript of <em>a</em> in the first term add up to <em>n</em> + 1.)
Denote the remaining sum by <em>S</em> ; then
Multiply both sides by 2 :
Subtract 2<em>S</em> from <em>S</em> to get
So, we end up with