How to prove with induction
In the recursive definition

$$ P(a,b) = \begin{cases} P(2a,\lfloor b/2 \rfloor) &amp; b &gt; 1, b \text{ even} \\
P(2a,\lfloor b/2 \rfloor) + a &amp; \text{if } b &gt; 1, b \text{ odd} \\
a &amp; \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 &lt; 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 &lt; 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$.