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.

  • $\begingroup$ can you explain why we do b=1 and not a =1 .. what are a , b in this type of functions ? and it would be very helpful if you could provide some links @tjhghley $\endgroup$ – Dana10 Oct 25 '16 at 20:03
  • $\begingroup$ The sub-function of the piecewise function is chosen based on the value of b, not a. In this function, a and b are just variables. $\endgroup$ – tjhighley Oct 25 '16 at 20:05
  • $\begingroup$ im still stuck on the prove i could do that , i would be glad if you show me how $\endgroup$ – Dana10 Oct 26 '16 at 9:05

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$.

  • $\begingroup$ but why did you add the a at the other side of the equation 2a⋅(b−1)/2+a=a(b−1)+a $\endgroup$ – Dana10 Oct 26 '16 at 23:58
  • $\begingroup$ We rewrite $P(a,b)$ using the definition as $P(2a,\lfloor b/2 \rfloor) + a$ and then we use the induction hypothesis and the properties of the floor operator to ger $2a \cdot (b-1)/2 +a = a(b-1) + a = a (b-1 + 1) = ab$. $\endgroup$ – Hans Hüttel Oct 27 '16 at 12:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.