Solve the recurrence relation $a_n=a_{n/2} +n +1$

Question

I don't know how to solve this question: Solve the recurrence relation $a_{n}=a_{n/2}+n+1$ with $a_1=1$.

Answer 1

Assumption. $n$ is a power of $2$.

Do a few substitutions to spot the pattern: \begin{align*} a_{n} & =a_{n/2}+n+1\\ & =a_{n/4}+n+n/2+1+1\\ & =a_{n/8}+n+n/2+n/4+1+1+1\\ & =\cdots \end{align*} Therefore, $$ a_{n} =\sum_{k=0}^{\lg_{2}n}2^{k}+\sum_{k=1}^{\lg_{2}n}1 =2n-1+\lg_{2}n. $$

Answer 2

Assume that $n=2^k$ for some nonnegative integer $k$, to avoid the case of non-integer indices. For $k=0,1,2,3$ we have \begin{align} a_1 &= 1\\ a_2 &= 4\\ a_4 &= 9\\ a_8 &= 18 \end{align} By observation, this follows the pattern $a_n=2n+\lg n-1$. Indeed, if we assume that $a_n=2n+\lg n-1$ for some $n=2^k$, $k\geqslant0$ then we have \begin{align} a_{2n} &= a_n + 2n + 1\\ &= 2n + \lg n -1 + 2n + 1\\ &= 2(2n) + \lg 2n -1, \end{align} so it follows by induction. (Note that $\lg 2n = \lg 2 + \lg n = 1 + \lg n$.)