3

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

mira
  • 31
  • 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 Answers3

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

Robert Israel
  • 448,999
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)$}$

cactus314
  • 24,438
  • 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
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.

Rick Decker
  • 8,718