Practice Problems for Chapter 6

🔗

Section 6.4 Practice Problems for Chapter 6

🔗

Exercises

🔗

1.

🔗

(a)

Calculate $1 + 3 + 5 + \dots + (2 n - 1)$ for several natural numbers $n .$

🔗

(b)

Based on your work in Task 6.4.1.a, if $n \in N,$ make a conjecture about the value of the sum $1 + 3 + 5 + \dots + (2 n - 1) = \sum_{j = 1}^{n} (2 j - 1) .$

🔗

(c)

Use mathematical induction to prove your conjecture in Task 6.4.1.b.

Solution.

🔗

Proof.

We will use a proof by mathematical induction. For each natural number $n,$ we let $P (n)$ be

1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

We first prove that $P (1)$ is true. Notice that when $n = 1,$ both the left and right sides of the equation for $P (n)$ are equal to 1. This proves that $P (1)$ is true.

For the inductive step, we prove that for each $k \in N,$ if $P (k)$ is true, then $P (k + 1)$ is true. So let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that

\begin{matrix} (11) & 1 + 3 + 5 + \dots + (2 k - 1) = k^{2} . \end{matrix}

The goal now is to prove that $P (k + 1)$ is true. That is, it must be proved that

\begin{aligned} 1 + 3 + 5 + \dots + (2 k - 1) + (2 (k + 1) - 1) & = (k + 1)^{2} \\ (12) & 1 + 3 + 5 + \dots + (2 k - 1) + (2 k + 1) & = (k + 1)^{2} \end{aligned}

To do this, we add $(2 k + 1)$ to both sides of equation (11), which gives

\begin{aligned} 1 + 3 + 5 + \dots + (2 k - 1) + (2 k + 1) & = k^{2} + k + 1 \\ = (k + 1)^{2} \end{aligned}

Comparing this result to equation (12), we see that if $P (k)$ is true, then $P (k + 1)$ is true. Hence, the inductive step has been established, and by the Principle of Mathematical Induction, we have proved that for each natural number $n,$ $1 + 3 + 5 + \dots + (2 n - 1) = n^{2} .$

🔗

2.

Prove the following:

Proposition. For each natural number $n,$ 3 divides $4^{n} \equiv 1 (\mod 3) .$

Solution.

🔗

Proof.

We will use a proof by mathematical induction. For each natural number $n,$ we let $P (n)$ be

4^{n} \equiv 1 (\mod 3)

We first prove that $P (1)$ is true. Notice that when $n = 1,$ $4^{n} = 4^{1} = 4$ and $4 \equiv 1 (\mod 3) .$ This proves that $P (1)$ is true.

For the inductive step, we prove that for each $k \in N,$ if $P (k)$ is true, then $P (k + 1)$ is true. So let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that

\begin{matrix} (13) & 4^{k} \equiv 1 (\mod 3) \end{matrix}

The goal now is to prove that $P (k + 1)$ is true. That is, it must be proved that

\begin{matrix} (14) & 4^{k + 1} \equiv 1 (\mod 3) \end{matrix}

Since we have to assume that $4^{k} \equiv 1 (\mod 3),$ we conclude that 3 divides $(4^{k} + 1)$ and so there exists and integer $m$ such that

4^{k} - 1 = 3 m .

Multiplying both sides of this equation by 4, we obtain

\begin{aligned} 4 (4^{k} + 1) & = 4 (3 m) \\ 4^{k + 1} - 4 & = 12 m \\ 4^{k + 1} - 3 - 1 & = 12 m \\ 4^{k + 1} - 1 & = 3 + 12 m \\ 4^{k + 1} - & 3 (1 + 4 m) \end{aligned}

So we have proved that if $P (k)$ is true, then $P (k + 1)$ is true. Hence, the inductive step has been established, and by the Principle of Mathematical Induction, we have proved that for each natural number $n,$ $4^{n} \equiv 1 (\mod 3) .$

🔗

3.

For which natural numbers $n$ is $3^{n}$ greater than $5 + 2^{n} ?$ State a proposition (with an appropriate quantifier) and prove it.

Solution.

Proposition. For each natural number $n$ with $n \geq 3,$ $3^{n} > 5 + 2^{n} .$

🔗

Proof.

We will use a proof by mathematical induction. For each natural number $n,$ we let $P (n)$ be

3^{n} > 5 + 2^{n}

We first prove that $P (3)$ is true. Notice that when $n = 3,$ $3^{n} = 27$ and $5 + 2^{n} = 13 .$ Since $27 > 13,$ this proves that $P (1)$ is true.

For the inductive step, we prove that for each $k \in N$ with $k \geq 3,$ if $P (k)$ is true, then $P (k + 1)$ is true. So let $k$ be a natural number with $k \geq 3$ and assume that $P (k)$ is true. That is, assume that

\begin{matrix} (15) & 3^{k} > 5 + 2^{k} \end{matrix}

The goal now is to prove that $P (k + 1)$ is true. That is, it must be proved that

\begin{matrix} (16) & 3^{k + 1} > 5 + 2^{k + 1} \end{matrix}

So we multiply both sides of inequality (15) to obtain

\begin{aligned} 3 \cdot 3^{k} & > 3 (5 + 2^{k}) \\ (17) & 3^{k + 1} & > 15 + 3 \cdot 2^{k} \end{aligned}

Since $3 > 2,$ $3 \cdot 2^{k} > 2 \cdot 2^{k}$ or $3 \cdot 2^{k} > 2^{k + 1} .$ In addition, $15 > 5$ and so we can co

🔗

4.

The Fibonacci numbers are a sequence of natural numbers $f_{1}, f_{2}, f_{3}, \dots, f_{n}, \dots$ defined recursively as follows:

$f_{1} = 1$ and $f_{2} = 1,$ and
For each natural number $n,$ $f_{n + 2} = f_{n + 1} + f_{n} .$

In words, the recursion formula states that for any natural number $n$ with $n =\geq 3,$ the $n^{t h}$ Fibonacci number is the sum of the two previous Fibonacci numbers. So we see that

\begin{aligned} f_{3} & = f_{2} + f_{1} = 1 + 1 = 2 \\ f_{4} & = f_{3} + f_{2} = 2 + 1 = 3, and \\ f_{5} & = f_{4} + f_{3} = 3 + 2 = 5 \end{aligned}

🔗

(a)

Calculate $f_{6}$ through $f_{20} .$

Solution.

\begin{aligned} f (5) & = 5 & f_{9} & = 34 & f_{13} & = 233 & f (17) & = 1597 \\ f (6) & = 8 & f_{10} & = 55 & f_{14} & = 377 & f (18) & = 2584 \\ f (7) & = 13 & f_{11} & = 89 & f_{15} & = 610 & f (19) & = 4181 \\ f (8) & = 21 & f_{12} & = 144 & f_{16} & = 987 & f (20) & = 6765 \end{aligned}

🔗

(b)

Is every third Fibonacci number even? That is it true that for each natural number $n,$ $f_{3 n}$ is even? Justify your conclusion.

Solution.

🔗

Proof.

We will use a proof by induction. For each natural number $n,$ we let $P (n)$ be,

$f_{3 n}$ is an even natural number.

Since

f_{3} = 2,

we see that

P (1)

is true and this proves the basis step.

For the inductive step, we let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that $f_{3 k}$ is an even natural number. This means that there exists an integer $m$ such that

\begin{matrix} (18) & f_{3 k} = 2 m . \end{matrix}

We need to prove that $P (k + 1)$ is true or that $f_{3 (k + 1)}$ is even. Notice that $3 (k + 1) = 3 k + 3$ and, hence, $f_{3 (k + 1)} = f_{3 k + 3} .$ We can now use the recursion formula for the Fibonacci numbers to conclude that

f_{3 k + 3} = f_{3 k + 2} + f_{3 k + 1} .

Using the recursion formula again, we get $f_{3 k + 2} = f_{3 k + 1} + f_{3 k} .$ Putting this all together, we see that

\begin{aligned} f_{3 (k + 1)} & = f_{3 k + 3} \\ = f_{3 k + 2} + f_{3 k + 1} \\ = (f_{3 k + 1} + f_{3 k}) + f_{3 k + 1} \\ (19) & = 2 f_{3 k + 1} + f_{3 k} \end{aligned}

We now substitute the expression for $f_{3 k}$ in equation (18) into equation (19). This gives

\begin{aligned} f_{3 (k + 1)} & = 2 f_{3 k + 1} + 2 m \\ f_{3 (k + 1)} & = 2 (f_{3 k + 1} + m) \end{aligned}

This preceding equation shows that $f_{3 (k + 1)}$ is even. Hence it has been proved that if $P (k)$ is true, then $P (k + 1)$ is true and the inductive step has been established. By the Principle of Mathematical Induction, this proves that for each natural number $n,$ the Fibonacci number $f_{3 n}$ is an even natural number.

🔗

(c)

Is it true that for each natural number $n$ with $n \geq 2,$ $f_{1} + f_{3} + \dots + f_{2 n - 1} = f_{n + 1} - 1 ?$ Justify your conclusion.

Solution.

🔗

Proof.

Let P(n) be “ $f_{1} + f_{2} + \dots + f_{n - 1} = f_{n + 1} - 1 .$ ” Since $f_{1} = f_{3} - 1,$ $P (2)$ is true, and this proves the basis step.

For the inductive step, we let $k$ be a natural number with $k \geq 2$ and assume that $P (k)$ is true and will prove that $P (k + 1)$ is true. That is, we assume that

\begin{matrix} (20) & f_{1} + f_{2} + \dots + f_{k - 1} = f_{k + 1} - 1, \end{matrix}

and will prove that

\begin{matrix} (21) & f_{1} + f_{2} + \dots + f_{k - 1} + f_{k} = f_{(k + 1) + 1} - 1 = f_{k + 2} - 1 . \end{matrix}

By adding $f_{k}$ to both sides of equation (20), we see that

\begin{aligned} (f_{1} + f_{2} + \dots + f_{k - 1}) + f_{k} & = (f_{k + 1} - 1) + f_{k} \\ = (f_{k + 1} + f_{k}) - 1 \\ = f_{k + 2} - 1 . \end{aligned}

Comparing this to equation (21), we see that we have proved that if $P (k)$ is true, then $P (k + 1)$ is true and the inductive step has been established. So by the Principle of Mathematical Induction, this proves that for each natural number n with $n \geq 2,$ $f_{1} + f_{3} + \dots + f_{2 n - 1} = f_{n + 1} - 1$

🔗

5.

Prove the following proposition using mathematical induction.

For each $n \in N$ with $n \geq 8,$ there exist nonnegative integers $x$ and $y$ such that $n = 3 x + 5 y .$

Suggestion: Use the Second Principle of Induction and have the basis step be a proof that $P (8),$ $P (9),$ and $P (10)$ are true using an appropriate open sentence for $P (n) .$

Solution.

🔗

Proof.

Proof. We will use a proof by mathematical induction. We let $P (n)$ be, “there exist nonnegative integers $x$ and $y$ such that $n = 3 x + 5 y .$ ”

Basis Step: For the basis step, we will show that $P (8),$ $P (9),$ and $P (10)$ are true. We see that

$P (8)$ is true since $3 \cdot 1 + 5 \cdot 1 = 8 .$
$P (9)$ is true since $3 \cdot 3 + 5 \cdot 0 = 9$
$P (10)$ is true since $3 \cdot 0 + 5 \cdot 2 = 10 .$

Inductive Step: Let $k \in N$ with $k \geq 10 .$ Assume that $P (8),$ $P (9),$ …, $P (k)$ are true. Now, notice that

k + 1 = 3 + (k - 2)

Since $k \geq 10,$ we can conclude that $k - 2 \geq 8$ and hence $P (k - 2)$ is true. Therefore, there exist non-negative integers $u$ and $v$ such that $k - 2 = (3 u + 5 v) .$ Using this equation, we see that

\begin{aligned} k + 1 & = 3 + (3 u + 5 v) \\ = 3 (1 + u) + 5 v . \end{aligned}

Hence, we can conclude that $P (k + 1)$ is true. This proves that if $P (8),$ $P (9),$ … , $P (k)$ are true, then $P (k)$ is true. Hence, by the Second Principle of Mathematical Induction, for all natural numbers $P (k + 1)$ with $n \geq 8,$ there exist nonnegative integers $x$ and $y$ such that $n = 3 x + 5 y .$

Constructing and Writing Mathematical Proofs: A Guide for Mathematics Students

Search Results:

Section 6.4 Practice Problems for Chapter 6

Exercises

1.

(a)

(b)

(c)

Proof.

2.

Proof.

3.

Proof.

4.

(a)

(b)

Proof.

(c)

Proof.

5.

Proof.