0
$\begingroup$

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

$\endgroup$
15
  • 1
    $\begingroup$ Welcome to Maths SX! Wouldn't it be $a_{n+1}=$ ? $\endgroup$
    – Bernard
    Aug 30, 2019 at 18:17
  • $\begingroup$ @Bernard It's $a_n=a_{n/2}+...$, based on the body of the question. $\endgroup$
    – Botond
    Aug 30, 2019 at 18:18
  • $\begingroup$ 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? $\endgroup$
    – Botond
    Aug 30, 2019 at 18:19
  • 1
    $\begingroup$ Bu if $n=3$, what happens? $\endgroup$
    – Matteo
    Aug 30, 2019 at 18:22
  • 2
    $\begingroup$ 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!". $\endgroup$
    – Botond
    Aug 30, 2019 at 18:22

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ i did'nt get this method.generally we solve recurrence relation problem by conerting into characteristics equation $\endgroup$ Aug 31, 2019 at 4:44
  • 1
    $\begingroup$ You can solve anything any way you want, as long as you get the right answer. The characteristic method is usually reserved for linear homogeneous recurrences (which this is not). $\endgroup$
    – parsiad
    Aug 31, 2019 at 6:28
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.