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
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
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)$.
The function $T(n) = \lfloor n/2 \rfloor $ can be found in 3 steps:
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)$}$
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.