Recurrence relation, find general term 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
 A: 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)$.
A: 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)$}$
A: 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.
