# Solve the recurrence relation $a_n=a_{n/2} +n +1$ [closed]

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

• Welcome to Maths SX! Wouldn't it be $a_{n+1}=$ ? Aug 30, 2019 at 18:17
• @Bernard It's $a_n=a_{n/2}+...$, based on the body of the question. Aug 30, 2019 at 18:18
• Did you try to solve the problem alone? What were your attempts? For example, did you try to calculate some of the values and try to find a pattern? Aug 30, 2019 at 18:19
• Bu if $n=3$, what happens? Aug 30, 2019 at 18:22
• Could you edit your question and include your work? People are more willing to help if you write down your own thoughts and not just tell them that "here is my homework, solve it for me!". Aug 30, 2019 at 18:22

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.$$
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$$.)