Sections 4.2,4.6.htm

Sections 4.2, 4.6

2. (a) We verify directly that is true, since $1^{3}-1=0$ is a multiple of .

Assume is true, so that $k^{3}-k$ is a multiple of . We show must also be true. But . Note that $k^{2}+k$ is always even as either the sum of two even numbers or the sum of two odd numbers, so $3(k^{2}+k)$ is necessarily a multiple of . But $k^{3}-k$ is a multiple of by assumption, so is a multiple of as the sum of two multiples of . In other words, is true whenever is true.

With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

3. Prove that for $n\in \QTR{bf}{P.}$

We verify directly that is true: while $\checkmark$

We show that for all $k\in \QTR{bf}{P.}$ So we assume that is true, and we MUST SHOW that

Well, (notation)

(substitute the induction hypothesis)

(algebra)

and we are done. With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

4. Prove for all $n\in \QTR{bf}{P.}$

Rephrased, prove that for all $n\in \QTR{bf}{P.}$

We verify directly that is true. The left side is $6\cdot 1-2=4$ , while the right hand side is $\checkmark$

We show that for all $k\in \QTR{bf}{P.}$ So we assume that and we MUST SHOW that

Well, (notation)

(substitute the induction hypothesis)

(algebra)

and we are done. With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

9. We verify directly that is true, since $11^{1}-4^{1}=7$ is a multiple of .

Assume is true, so that $11^{k}-4^{k}$ is a multiple of . We show must also be true. But . Note that $7\cdot 4^{k}$ is clearly a multiple of , and $11^{k}-4^{k}$ is a multiple of by assumption. So $11^{k+1}-4^{k+1}$ is a multiple of as the sum of two multiples of . In other words, is true whenever is true.

With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction

12. We verify directly that is true, since $2^{2}=4>3=2+1$ .

Assume is true, so that $k^{2}>k+1$ . We show must also be true. But since $k^{2}>k+1$ by assumption and for $k\geq 2$ . In other words, is true whenever is true.

With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

13. a)

	sum

Based on these results, we might hypothesize that

(b) We verify directly that is true, since $1=1^{2}$ .

Assume is true, so that . We show must also be true. (by induction hypothesis and simplification) . In other words, is true whenever is true.

With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

16. Prove for all $n\in \QTR{bf}{P.}$

Rephrased, prove that for all $n\in \QTR{bf}{P.}$

We verify directly that is true. The left side is , while the right hand side is $3\cdot 1^{2}=3$ $\checkmark$

We show that for all $k\in \QTR{bf}{P.}$ So we assume that and we MUST SHOW that

Well, (notation)

(We include the term in the sum, then subtract it off)

(We separate the two 'top' terms off from the sum)

(substitute the induction hypothesis)

(algebra)

and we are done. With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

17. Prove that $5^{n}-4n-1$ is divisible by 16 for all $n\in \QTR{bf}{P.}$

We verify directly that is true. The expression $5^{n}-4n-1$ becomes on substituting , which gives , and $16\mid 0.$ $\ \ \ \checkmark$

We show that for all $k\in \QTR{bf}{P.}$ So we assume that $16\mid 5^{k}-4k-1,$ and we prove that $\ \ .$ So we are assuming that $5^{k}-4k-1=16m$ for some $m\in \QTR{bf}{Z,}$ and we MUST SHOW that for some $n\in \QTR{bf}{Z.}$ $\ \$

Well, (notation and algebra)

(substitute for $5^{k}$ from the induction hypothesis)

(algebra)

some integer)

and we are done. With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

Section 4.6:

2a. Prove for all $n\in \QTR{bf}{P.}$

Rephrased, prove that for all $n\in \QTR{bf}{P.}$

We verify directly that is true. The left side is $1\cdot 2=2$ , while the right hand side is $\checkmark$

We show that for all $k\in \QTR{bf}{P.}$ So we assume that and we MUST SHOW that

Well, (notation)

(substitute the induction hypothesis)

(algebra)

and we are done. With the basis and inductive step verified, our proof is complete by the Principle of Mathematical Induction.

3. Prove that $n^{5}-n$ is divisible by 10 for all $n\in \QTR{bf}{P.}$

We verify directly that is true. The expression $n^{5}-n$ becomes $1^{5}-1$ on substituting , which gives , and $10\mid 0.$ $\ \ \ \checkmark$

We show that for all $k\in \QTR{bf}{P.}$ So we assume that $10\mid k^{5}-k,$ and we prove that $\ \ .$ So we are assuming that $k^{5}-k=10m$ for some $m\in \QTR{bf}{Z,}$ and we MUST SHOW that for some $n\in \QTR{bf}{Z.}$ $\ \$

Well, (algebra)

(algebra)

(substituting the induction hypothesis)

Now there are two cases: is even, and is odd. If is even, then for some integer , in which case the expression $5k(k^{3}+1)$ becomes $10p(k^{3}+1)$ , or where $s\in \QTR{bf}{Z}$ .. If is odd, then $k^{3}$ is odd, so that $k^{3}+1$ is even, so that $k^{3}+1=2t$ where $t\in \QTR{bf}{Z,}$ so that the expression $5k(k^{3}+1)$ becomes $5k\cdot 2t=10s$ where $s\in \QTR{bf}{Z.}$ Thus in either case we can continue the previous work and get: