Solve recurrence formula

Question

Thanks! That helps a lot. I think the substituting is the way to go

Answer 1

I have an interesting way to get to the answer, which I believe is

$$T(n) = \frac{2^{2 n}}{4 n 3^n}$$

for $n \ge 1$. Let $n=2^k$. Then define $U_k=T(2^k)$. You get the recursion

$$U_k=2^k U_{k-1}^2$$

$$U_0=1/3$$

By some playing around and induction, I got the following solution:

$$U_k = \frac{2^{f(k)}}{3^{2^k}}$$

where

$$f(k) = \sum_{m=1}^k (k-m+1)2^{m-1} = 2^{k+1}-(k+2)$$

How did I get this? I played around with the first few terms and established a pattern:

$$U_0=\frac{1}{3}$$ $$U_1 = \frac{2^1}{3^2}$$ $$U_2 = \frac{2^{2+2\cdot 1}}{3^4}$$ $$U_3 = \frac{2^{3+(2\cdot(2+2\cdot1))}}{3^8}$$

Carry on forming the exponent in the numerator, and you will see how I got $f(k)$. The stated result follows, because you can rewrite this expression for $U$ as

$$U_k = \frac{\left(2^{2^k} \right )^2}{4 \cdot 2^k 3^{2^k}} = T(2^k)$$

Plug $n=2^k$ and you get the above expression.

Answer 2

There is a linear recurrence formula hidden not far.

By the change of varibale $n=2^k$ and setting $x_k:=T(2^k)$, the problem amounts to solving $$ x_k=2^kx_{k-1}^2\qquad x_0=\frac{1}{3}. $$ Of course, $x_k>0$ for all $k$ by induction, so we consider the sequence $y_k=\log_2x_k$, which satisfies $$ y_k=2y_{k-1}+k\qquad y_0=-\log_23. $$ The general solution of the homogeneous part is $C2^k$. And by the method of undetermined coefficients, we look for a particular solution of the form $y_k=Ak+B$. Plugging this is the reccurrence formula yields $A=-1$ and $B=-2$. So the general solution is: $$ y_k=C2^k-k-2. $$ Given $y_0=C-2=-\log_23$, we get $$ y_k=(2-\log_23)2^k-k-2 $$ hence $$ x_k=2^{(2-\log_23)2^k-k-2}\quad\Rightarrow\quad x_k=\frac{2^{2^{k+1}}}{2^{k+2}3^{2^k}}. $$ Going back to $T(n)$, this gives $$ T(n)=\frac{4^{n-1}}{n3^n}. $$