An arithmetic function is defined as follows:$f(1)=1$, $f(2k)=k$ and $f(2k+1)=f(k)+f(k+1)$. When (for which $k$) is $f(k)$ even?
While it is obvious that $f(4n-1)=f(4n)=2n$, therefore $f(k)$ is even for $k=4n$ and $k=4n-1$, which is possible to prove using induction (isn't it?), I don't know how to prove the converse.
I tried to solve the recurrence or make use of constant difference between certain elements of the sequence $\ldots$ What am I missing?
Thank you.
Your function has the closed form $$ f(k) = \lfloor (k+1)/2 \rfloor $$ for all $k$. For even $k$, both sides are equal to $k/2$. For odd $k$, it can be proved by induction.
If follows that $f(k)$ is even exactly for $k = 4n$ and $k = 4n-1$.