Solving a Recurrence in Terms of k

Question

I have this recurrence relation: $$t(2^{2^{k}}) = 1+t(\sqrt{(2^{2^k}})$$

How do I express it in terms of $k$, i.e. $t(k)$? I've tried using logarithm properties to no avail.

Edit: I've tried isolating $k$, and I've ended up getting something like this: $$t(k) = 1+t\Big(\sqrt{\Big(\frac{\log(\frac{\log(2^{2^{k}})}{\log(2)})}{\log(2)}}\Big)\Big)$$

@brilhana Which $k$ is an integer - the one in $t(2^{2^k})$ or the one in $t(k)$? Btw, that big radical on the RHS simplifies to $\sqrt{k}$. — dxiv, Nov 14 '16 at 06:34

hamam_Abdallah · Answer 1 · 2016-11-14T10:41:00.010

1

Put

$f(k)=t(2^{2^k})=1+f(k-1)$

$\implies$

$f(k)=k+f(0)=k+t(2)$

if $K=2^{2^k} $ then

$2^k=\log_2(K)$ and

$k=\log_2(\log_2(K))$

thus

$$t(k)=\log_2(\log_2(k))+t(2).$$

edited Nov 14 '16 at 10:41

answered Nov 14 '16 at 07:30

hamam_Abdallah

62,951

Solving a Recurrence in Terms of k

1 Answers1