Answer to Question #284743 in Discrete Mathematics for Rakibul islam

Question

4. Let P(n) be the statement that 1+2+...+n'3D (n(n + 1)/2)2 for the positive integer n. a) What is the statement P(1)? b) Show that P(1) is true, completing the basis step of the proof. c) What is the inductive hypothesis? d) What do you need to prove in the inductive step? e) Complete the inductive step, identifying where you use the inductive hypothesis. f) Explain why these steps show that this formula is true whenever n is a positive integer. 5. Prove that 12+32+52+ + (2n + 1)² = (n + 1)

Answer 1

4. Let $P(n)$ be the proposition that $1^3+2^3+...+n^3=(\dfrac{n(n+1)}{2})^2$ for the positive integer $n.$

(a) $P(1)$ is the statement that $1^3=(\dfrac{1(1+1)}{2})^2.$

(b) Basic Step

$P(1)$ is true because

$$1^3=1=(\dfrac{1(1+1)}{2})^2$$

This completes the basis step.

(c) For the inductive hypothesis, we assume that $P(k)$ is true for an arbitrary

positive integer $k.$ That is, we assume that

$$1^3+2^3+...+k^3=(\dfrac{k(k+1)}{2})^2$$

(d) Inductive Step

To carry out the inductive step we must show that when we assume that $P(k)$ is true, then $P(k + 1)$ is also true. That is, we must show that

$$1^3+2^3+...+k^3+(k+1)^3=(\dfrac{(k+1)(k+1+1)}{2})^2$$

assuming the inductive hypothesis $P(k).$

(e) Under the assumption of $P(k),$ we see that

$$1^3+2^3+...+k^3+(k+1)^3=$$

$$=(\dfrac{k(k+1)}{2})^2+(k+1)^3=$$

$$=(\dfrac{k+1}{2})^2(k^2+4(k+1))$$

$$=(\dfrac{k+1}{2})^2(k+2)^2$$

$$=(\dfrac{(k+1)(k+1+1)}{2})^2$$

Note that we used the inductive hypothesis in the second equation in this string of equalities to replace $1^3+2^3+...+k^3$ by $(\dfrac{k(k+1)}{2})^2.$

We have completed the inductive step.

(f) Because we have completed the basis step and the inductive step, by mathematical induction we know that $P(n)$ is true for all positve integers $n.$ That is, $1^3+2^3+...+n^3=(\dfrac{n(n+1)}{2})^2$ for the positive integer $n.$

5. Let $P(n)$ be the proposition that

$$1^2+3^2+5^2+...+(2n+1)^2$$

$$=\dfrac{(n+1)(2n+1)(2n+3)}{3}$$

for the nonnegative integer $n.$

(a) $P(0)$ is the statement that

$$(2(0)+1)^2=\dfrac{(0+1)(2(0)+1)(2(0)+3)}{3}.$$

(b) Basic Step

$P(0)$ is true because

$$(2(0)+1)^2=1=\dfrac{(0+1)(2(0)+1)(2(0)+3)}{3}.$$

This completes the basis step.

(c) For the inductive hypothesis, we assume that $P(k)$ is true for an arbitrary

nonnegative integer $k.$ That is, we assume that

$$1^2+3^2+...+(2k+1)^2=\dfrac{(k+1)(2k+1)(2k+3)}{3}$$

(d) Inductive Step

To carry out the inductive step we must show that when we assume that $P(k)$ is true, then $P(k + 1)$ is also true. That is, we must show that

$$1^2+3^2+...+(2k+1)^2+(2(k+1)+1)^2$$

$$=\dfrac{(k+1+1)(2(k+1)+1)(2(k+1)+3)}{3}$$

assuming the inductive hypothesis $P(k).$

(e) Under the assumption of $P(k),$ we see that

$$1^2+3^2+...+(2k+1)^2+(2(k+1)+1)^2$$

$$=\dfrac{(k+1)(2k+1)(2k+3)}{3}+(2(k+1)+1)^2$$

$$=\dfrac{(2k+3)(2k^2+3k+1+6k+9)}{3}$$

$$=\dfrac{(2k+3)(2k^2+9k+10)}{3}$$

$$=\dfrac{(2k+3)(k+2)(2k+5)}{3}$$

$$=\dfrac{(k+1+1)(2(k+1)+1)(2(k+1)+3)}{3}$$

Note that we used the inductive hypothesis in the second equation in this string of equalities to replace

$$1^2+3^2+...+(2k+1)^2+(2(k+1)+1)^2$$

by $\dfrac{(k+1)(2k+1)(2k+3)}{3}.$

We have completed the inductive step.

(f) Because we have completed the basis step and the inductive step, by mathematical induction we know that $P(n)$ is true for all nonnegative integers $n.$ That is,

$$1^2+3^2+5^2+...+(2n+1)^2$$

$$=\dfrac{(n+1)(2n+1)(2n+3)}{3}$$

for the nonnegative integer $n.$