Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do you find the general term of this recurrence relation?

$A(n)=c n+A(\lfloor n/2 \rfloor)$ for $n>2$, $ A(n) = 1 $ for $n=2$, where $c$-constant

share|improve this question
    
What have you tried? Since the lower index term depends on the floor of $n/2$, you might try separating even and odd entries to see if a pattern emerges. Don't we also need to know $A(1)$? –  hardmath Oct 11 '12 at 16:03

3 Answers 3

Let $b_j(n)$ be the $j$'th digit from the left in the binary expansion of $n$, and $s(n)$ the sum of the binary digits of $n$. Thus since $6 = 110_2$, $b_1(6) = b_2(6) = 1$, $b_3(6)=0$, and $s(6) = 2$. Then $A(n) = 2 n - s(n) + 1 - 3 c + (A(1) - 1 + 2 c) b_2(n)$.

share|improve this answer

The function $T(n) = \lfloor n/2 \rfloor $ can be found in 3 steps:

  • takes the binary expansion,
  • shifts the decimal point to the left
  • cut off the remainder

e.g. $ \lfloor 7/2\rfloor = \lfloor 111_2/10_2\rfloor = 11_2=3 \hspace{0.25in}\lfloor 3\pi /2 \rfloor = 4$

We can hit this recursion a few times, let $m = \lfloor \log_2 n \rfloor+1$ be the number of digits.

\begin{eqnarray} A(n) &=& cn + A(T(n)) \\ &=& c(n + T(n)) + A(T^2(n)) \\ &=& \dots \\ &=& c(n + T(n) + T^2(n) + \dots + T^{m}(n)) + A(T^{m}(n))\end{eqnarray} The last term $A(T^m(n)) = 0$ since we have shifted the decimal point left as many places as we have digits.

What does this expression mean? $S(n) \equiv n + T(n) + T^2(n) + \dots + T^{m}(n) $

For $n = 2^4$, $S(16) = 16 + 8 + 4 + 2 + 1 = 11111_2 = 31 = 2(16) - 1$.

For $n = 13=1101_2$ we get \begin{eqnarray}S(13) &=& 1101_2 + 110_2 + 11_2 + 1_2 \\ &=& 1111_2 + 111_2 + 1_2 \\&=& (10000_2 - 1)+ (1000_2 - 1) + (1_2- 1) \\ &=& 2\cdot 13 - 3 = \fbox{23}\end{eqnarray}

So $S(n) = 2n - \# \text{digits}(n)$ and $A(n) = \fbox{ $ c\Big(2n - \# \text{ digits}(n) \Big)$}$

share|improve this answer
    
It's not quite right. For example, $A(2) = 1$ but your formula would have $A(2) = c$ (where I'm interpreting "#digits" as number of 1's in the binary expansion). –  Robert Israel Oct 11 '12 at 17:52

Robert has shown an exact expression for $A(n)$, but if you'll settle for bounds on the sequence (and are willing to define $A(1) = 1-2c$, so that you'll have $A(2)=A(1)+2c$), then it's easy to show inductively that $$ 1+(2n-4-\lfloor\log_2 n\rfloor)c \le A(n)\le 1+(2n-4)c $$ The upper bound, by the way, is exact when $n$ is a power of 2.

Nothing surprising here, since this is a consequence of Robert's answer, but at least it's tidy.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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