1

Is there an exact (and if not, an asymptotic) solution to the following recurrence relation? $$ T(n) = 2^n T(n-1) + 2^n, \text{for } n > 0 $$

If yes, I'd also like to know whether this relation is an instance of a more general class of relations for which you can apply the same technique for solving it.

Mo B.
  • 165

1 Answers1

3

A sketch:

  • Let $u_n$ denote the value of $T(n)$ obtained if $T(0)=0$. Prove by induction $T(n)=2^{n(n+1)/2}T(0)+u_n$.

  • Define $v_n:=u_n/2^{n(n+1)/2}$ so $T(n)=2^{n(n+1)/2}(T(0)+v_n)$. Prove by induction $v_n=v_{n-1}+2^{-n(n-1)/2}$.

  • Since $v_0=0$, $T(n)=2^{n(n+1)/2}(T(0)+\sum_{k=1}^n2^{-k(k-1)/2})$.

J.G.
  • 115,835
  • Sorry, I don't understand the definition of $u_n$: what is meant by "the value of $T(n)$ obtained if $T(0) = 0$"? – Mo B. Jan 23 '21 at 15:19
  • @MoB. You defined a family of sequences parameterized by $T(0)$, so I expressed each such sequence in terms of the one with $T(0)=0$. – J.G. Jan 23 '21 at 15:22
  • That makes sense, thanks. – Mo B. Jan 23 '21 at 15:25