I'm still new to the whole proof thing (first class of discrete mathematics and analysis right now). I could do general induction problems, but the fact that 'n' is the output here along with the string of {0, 1} kind of throws me off. So far I kind of have
Base case: P(0) is true because b(0) = 0; P(1) is true because b(1) = (1)(1) = 1; P(2) is true because b(01) = (0)(1) + (1)(2) = 2; P(3) is true because b(11) = (1)(1) + (1)(2) = 3.
Now, let n >0. Assume that P(m) is true, where 0 <= m < n.
I don't know where to go from here, nor if I know if I did this first step right. Help please! Thanks.
I think we can do as follows: suppose the claim is true up to $\;n\in\Bbb N=\Bbb Z_{\ge0}\;$, and we shall show for $\;n+1\;$ . We have two cases, and we assume $\;n=b(\sigma_0\sigma_1\ldots\sigma_d)\;$:
1) $\;n\;$ is even: then$\;\sigma_0=0\;$ (why?) , and thus
$$b(1\sigma_0\sigma_1\ldots\sigma_d)=n+1$$
2) $\;n\;$ is odd: then $\;\sigma_0=1\;$ (again, why? Each why so far also answers the other one), so we define "summing in modulo two carrying", meaning: every time we get zero we "carry one" to the next digit (all the time from left to right!) , so if we had a $\;1\;$ we'll get a zero ($\;1+1=0$) and again carry one, and if we had a zero we'll get a one and carry nothing
For example
$$b(101101)=45\implies \begin{align}&101101\\&+\\&1\\&--------\\&011101\end{align} \implies b(011101)=46$$
or also $${}$$
$$b(111011)=55\implies \begin{align}&111011\\&+\\&1\\&--------\\&000111\end{align} \implies b(000111)=56$$