1

$G(k) = 2^{(1.5)\cdot 2^k}G(k-1) + \left(2 ^{3 \cdot (2^k)}\right)\left(2 ^{ (2k)}\right) \cdot k$

G(1) = c

I could not get any development that converged into anything. Can you please help to how to start?

EDIT:

I have started with other recurrence relation $T(n) = n^{\frac{3}{2}}T \left(n^{\frac{1}{2}} \right) + n^3 \log^2(n)\log(\log(n))$ and got G(k) after 2 variable replacements. now need to continue with G(k) but I'm stuck here

michal shapir
  • 11

1 Answers1

1

This is a linear recurrence with solution $G(k) = G_h(k)+G_p(k)$ with

$$ G_h(k)- 2^{\frac 32 2^k}G_h(k-1)=0\\ G_p(k)- 2^{\frac 32 2^k}G_p(k-1)=2^{3\times 2^k}2^{2k}k\\ $$

for the homogeneous term we have

$$ G_h(k) = C_0 8^{2^k} $$

now making

$$ G_p(k) = C_0(k) 8^{2^k} $$

we have after substitution

$$ C_0(k) -C_0(k-1) = 2^{2k} k $$

which has as solution

$$ C_0(k) = \frac 49\left(1+2^{2k}(3k-1)\right) $$

hence

$$ G(k) = C_0 8^{2^k}+\frac 49\left(1+2^{2k}(3k-1)\right)8^{2^k} $$

Cesareo
  • 33,252