Solve the following recurrence $f(n) = 2^n f(n - 1) + 2^n$ given $f(0)=1$. Solve the recurrence $f(n) = 2^n f(n - 1) + 2^n$ given $f(0)=1$.
The pattern I can come up with is 
$2^{2n-1} f(n - 2) + 2^{3n-1}$
$2^{3n-3} f(n - 3) + 2^{6n-4}$
$2^{4n-6} f(n - 4) + 2^{10n-10}$
How do I solve the recurrence relation from this pattern? Thanks.
 A: We have
$f(n) = 2^n f(n - 1) + 2^n
$.
Since
$\sum_{k=1}^n k
= n(n+1)/2
$,
divide the recurrence by
$2^{ n(n+1)/2}$.
It becomes
$\dfrac{f(n)}{2^{ n(n+1)/2}} 
=  \dfrac{f(n - 1)}{2^{ n(n+1)/2-n}} + \dfrac1{{2^{ n(n+1)/2-n}}}
=  \dfrac{f(n - 1)}{2^{ n(n-1)/2}} + \dfrac1{{2^{ n(n-1)/2}}}
$.
Now,
let
$g(n)
=\dfrac{f(n)}{2^{ n(n+1)/2}} 
$.
Then
$g(n-1)
=\dfrac{f(n-1)}{2^{ (n-1)n/2}} 
$
so the recurrence becomes
$g(n)
=  g(n-1) + \dfrac1{{2^{ n(n-1)/2}}}
$,
or
$g(n)-  g(n-1) 
= \dfrac1{{2^{ n(n-1)/2}}}
$.
Summing,
$g(n)-g(0)
=\sum_{k=1}^n (g(k_)-g(k-1))
=\sum_{k=1}^n \dfrac1{{2^{ k(k-1)/2}}}
$,
or
$\dfrac{f(n)}{2^{ n(n+1)/2}} -f(0)
=\sum_{k=1}^n \dfrac1{{2^{ k(k-1)/2}}}
$
or
$f(n)
=2^{ n(n+1)/2}+2^{ n(n+1)/2}\sum_{k=1}^n \dfrac1{{2^{ k(k-1)/2}}}
$.
Solving this involves summing
$\sum_{n=1}^m \dfrac1{{2^{ n(n-1)/2}}}
$.
I don't know how to sum this,
so I'll leave it here.

(added later)
Following up on my thought
that this looked
like a theta function,
I looked in good old
Whittaker and Watson.
In section 21.11,
page 464,
I find this 
(with a script theta that I don't know
how to enter):
$\theta_2(z, q)
=2\sum_{n=0}^{\infty} q^{(n+1/2)^2}\cos((2n+1)z)
$.
Therefore
$\begin{array}\\
\theta_2(0, q)
&=2\sum_{n=0}^{\infty} q^{(n+1/2)^2}\\
&=2q^{1/4}\sum_{n=0}^{\infty} q^{n^2+n}\\
\text{so}\\
\theta_2(0, r^{1/2})
&=2r^{1/8}\sum_{n=0}^{\infty} r^{(n^2+n)/2}
\qquad q = r^{1/2}\\
\text{so}\\
\theta_2(0, (1/2)^{1/2})
&=2(1/2)^{1/8}\sum_{n=0}^{\infty} (1/2)^{(n^2+n)/2}\\
&=2^{7/8}\sum_{n=0}^{\infty} (1/2)^{(n^2+n)/2}
\qquad r = 1/2\\
\end{array}
$
Therefore
$\sum_{n=0}^{\infty} \dfrac1{2^{(n^2+n)/2}}
=2^{-7/8}\theta_2(0, (1/2)^{1/2})
$.
