3
$\begingroup$

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

  • 0
    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)$?2012-10-11

3 Answers 3

1

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

0

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

  • 0
    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).2012-10-11
0

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.