So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction.
P(2·a,⌊b/2⌋) : b>1 and b is even number
P(a,b):= P(2·a,⌊b/2⌋)+a : b>1 and b is odd number
a :b=1
to prove is for all a,b ∈ N+ -> P(a,b)=a·b
Please don't show me the proof but how to deal with this kind of question.
Thank you
The first step is the basis step (or base case). For this problem, that is when $b = 1$. We identify that as the base case because $P(a, b)$ is a piece-wise function, and the non-recursive case is the base case. So prove that $P(a,b) = ab$ when $b=1$.
The inductive step will be a proof by cases because there are two recursive cases in the piecewise function: $b$ is even and $b$ is odd. Prove each separately.
The induction hypothesis is that $P(a,b_0) = ab_0$. You want to prove that $P(a,b_0+1)=a(b_0+1)$.
For the even case, assume $b_0 > 1$ and $b_0$ is even. Then show that $P(a,b_0+1)=P(2·a,⌊(b_0+1)/2⌋)=a(b_0+1)$. Prove this with a substitution based on the induction hypothesis.
After you complete the proof for the even case, do the same for the odd case.
In the recursive definition
$$ P(a,b) = \begin{cases} P(2a,\lfloor b/2 \rfloor) & b > 1, b \text{ even} \\ P(2a,\lfloor b/2 \rfloor) + a & \text{if } b > 1, b \text{ odd} \\ a & \text{if } b = 1 \end{cases} $$
the value of $b$ always decreases in a recursive call. Therefore you should prove the property $P(a,b) = a \cdot b$ by induction in $b$. We use the strong induction principle.
Base case - $b=1$: $P(a,1) = a$ and $a \cdot 1 = a$.
Inductive step - assume for all $k < n$, prove for $n$:
Suppose $b$ is even. We then have $P(a,b) = P(2a,\lfloor b/2 \rfloor)$. Since $b$ is even, we have $\lfloor b/2 \rfloor = b/2$. Since $\lfloor b/2 \rfloor < b$, we have by induction hypothesis that $P(2a,\lfloor b/2 \rfloor) = 2a \cdot \lfloor b/2 \rfloor = 2a \cdot b/2 = a \cdot b$.
Suppose $b$ is odd. Since $b$ is odd, we have $\lfloor b/2 \rfloor = (b-1)/2$. We now have $P(a,b) = P(2a,\lfloor b/2 \rfloor) + a = 2a \cdot (b-1)/2 +a = a(b-1) + a = a (b-1 + 1) = ab$.
