Help with proof regarding generalization of a function: $f(x)=2x+1-2^{\lfloor \log_2x\rfloor+1}$ Consider the below function: $$f(x)=2x+1-2^{\lfloor \log_2x\rfloor+1}$$
Let $f^x(x)$ refer to the composition of $f(x)$, $x$ number of times.

Now after having observed some patterns, I've hypothesized that: 
$$f^x(x)=2^y-1$$
Where:


*

*$x=2^{a_1}+2^{a_2}\cdot \cdot + 2^{a_y}$

*$\{a_1,a_2\cdot\cdot\cdot\cdot a_y\}$ All elements in this set are distinct, and $\in \{Z^++\{0\}\}$ (i.e. belong to the set of non-negative numbers).    

*$x \in Z^+$



How can I go about proving this? 
 A: Short version: if you use binary numbers, then your function removes the leading bit, shifts all remaining bits up by $1$, and adds a $1$ to the ones place. With this understanding, your observation is clear. 
For example, with $n=37$, in binary that is $100101$ with $y=3$. And applying the sequence I described above: $$\color{blue}100\color{magenta}10\color{green}1\to\color{magenta}10\color{green}11\to\color{green}111\to111\to\ldots\to111=1000-1$$

All numbers below are in binary (except the ones in the limits of summation and in the exponents).
Your function is 
$$f(x)=10x+1-10^{\lfloor\log_{10}x\rfloor+1}$$ 
Let $n$ be an integer. So $n=\sum_{k=1}^y10^{a_k}$. Then $$\begin{align}
f(n)&=\sum_{k=1}^y10^{a_k+1}+1-10^{a_y+1}=\sum_{k=1}^{y-1}10^{a_k+1}+1\\
f(f(n))&=\sum_{k=1}^{y-1}10^{a_k+2}+10+1-10^{a_{y-1}+2}=\sum_{k=1}^{y-2}10^{a_k+2}+10+1\\
f^{3}(n)&=\sum_{k=1}^{y-2}10^{a_k+3}+100+10+1-10^{a_{y-2}+3}=\sum_{k=1}^{y-3}10^{a_k+3}+100+10+1=\sum_{k=1}^{y-3}10^{a_k+3}+\sum_{i=0}^210^i
\end{align}$$
This can continue, inductively. Note that the largest term here is in the first sum, so the floored logarithm will always be defined from that. This gives $$f^m(n)=\sum_{k=1}^{y-m}10^{a_k+m}+\sum_{i=0}^{m-1}10^i$$
for $m\leq y$. This eventually brings you to $m=y$:
$$f^{y}(n)=\sum_{i=0}^{y-1}10^i=10^y-1$$
which is not quite what your statement says. 
But if you keep going from here: 
$$\begin{align}
f(f^{y}(n))&=10^{y+1}-10+1-10^y\\
&=(10^{y}+10^y)-(1+1)+1-10^y\\
&=10^{y}-1
\end{align}$$ 
So at this point further composition with $f$ fixes the output. Since $n>y$, this gives you $$f^{n}(n)=10^y-1$$ as stated.
