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.
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}) $.
