2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\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
0
$\begingroup$

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

$\endgroup$
  • $\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.