Skip to main content

Section 6.4 Practice Problems for ChapterĀ 6

Exercises

1.

(a)

Calculate \(1 + 3 + 5 + \cdots + (2n - 1)\) for several natural numbers \(n\text{.}\)

(b)

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

(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\text{,}\) we let \(P(n)\) be

\begin{equation*} 1 + 3 + 5 + \cdots + (2n - 1) = n^2 \end{equation*}

We first prove that \(P (1)\) is true. Notice that when \(n = 1\text{,}\) 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\text{,}\) 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{equation} 1 + 3 + 5 + \cdots + (2k - 1) = k^2\text{.}\tag{11} \end{equation}

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

\begin{align} 1 + 3 + 5 + \cdots + (2k - 1) + (2(k + 1) - 1) \amp = (k + 1)^2\notag\\ 1 + 3 + 5 + \cdots + (2k - 1) + (2k + 1) \amp = (k + 1)^2\tag{12} \end{align}

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

\begin{align*} 1 + 3 + 5 + \cdots + (2k - 1) + (2k + 1) \amp = k^2 + k + 1\\ \amp = (k + 1)^2 \end{align*}

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\text{,}\) \(1 + 3 + 5 + \cdots + (2n - 1) = n^2\text{.}\)

2.

Prove the following:

Proposition. For each natural number \(n\text{,}\) 3 divides \(\modulo{4^n}{1}{3}\text{.}\)

Solution.
Proof.

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

\begin{equation*} \modulo{4^n}{1}{3} \end{equation*}

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

For the inductive step, we prove that for each \(k \in \N\text{,}\) 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{equation} \modulo{4^k}{1}{3}\tag{13} \end{equation}

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

\begin{equation} \modulo{4^{k+1}}{1}{3}\tag{14} \end{equation}

Since we have to assume that \(\modulo{4^k}{1}{3}\text{,}\) we conclude that 3 divides \(\left( 4^k + 1 \right)\) and so there exists and integer \(m\) such that

\begin{equation*} 4^k - 1 = 3m\text{.} \end{equation*}

Multiplying both sides of this equation by 4, we obtain

\begin{align*} 4 \left( 4^k + 1 \right) \amp = 4(3m)\\ 4^{k + 1} - 4 \amp = 12m\\ 4^{k + 1} - 3 - 1 \amp = 12m\\ 4^{k + 1} - 1 \amp = 3 + 12m\\ 4^{k + 1} - \amp 3( 1 + 4m) \end{align*}

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\text{,}\) \(\modulo{4^n}{1}{3}\text{.}\)

3.

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

Solution.

Proposition. For each natural number \(n\) with \(n \geq 3\text{,}\) \(3^n \gt 5 + 2^n\text{.}\)

Proof.

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

\begin{equation*} 3^n \gt 5 + 2^n \end{equation*}

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

For the inductive step, we prove that for each \(k \in \N\) with \(k \geq 3\text{,}\) 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{equation} 3^k \gt 5 + 2^k\tag{15} \end{equation}

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

\begin{equation} 3^{k+1} \gt 5 + 2^{k+1}\tag{16} \end{equation}

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

\begin{align} 3 \cdot 3^k \amp \gt 3(5 + 2^k)\notag\\ 3^{k + 1} \amp \gt 15 + 3 \cdot 2^k\tag{17} \end{align}

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

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\text{,}\) \(\modulo{4^n}{1}{3}\text{.}\)

4.

The Fibonacci numbers are a sequence of natural numbers \(f_1, f_2, f_3, \ldots, f_n, \ldots\) defined recursively as follows:

  • \(f_1 = 1\) and \(f_2 = 1\text{,}\) and

  • For each natural number \(n\text{,}\) \(f_{n + 2} = f_{n + 1} + f_n\text{.}\)

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

\begin{align*} f_3 \amp = f_2 + f_1 = 1 + 1 = 2\\ f_4 \amp = f_3 + f_2 = 2 + 1 = 3 \text{, and }\\ f_5 \amp = f_4 + f_3 = 3 + 2 = 5 \end{align*}
(a)

Calculate \(f_6\) through \(f_{20}\text{.}\)

Solution.
\begin{align*} f(5) \amp = 5 \amp f_9 \amp = 34 \amp f_{13} \amp = 233 \amp f(17) \amp = 1597\\ f(6) \amp = 8 \amp f_{10} \amp = 55 \amp f_{14} \amp = 377 \amp f(18) \amp = 2584\\ f(7) \amp = 13 \amp f_{11} \amp = 89 \amp f_{15} \amp = 610 \amp f(19) \amp = 4181\\ f(8) \amp = 21 \amp f_{12} \amp = 144 \amp f_{16} \amp = 987 \amp f(20) \amp = 6765 \end{align*}
(b)

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

Solution.
Proof.

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

\(f_{3n}\) is an even natural number.
Since \(f_3 = 2\text{,}\) 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_{3k}\) is an even natural number. This means that there exists an integer \(m\) such that

\begin{equation} f_{3k} = 2m\text{.}\tag{18} \end{equation}

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

\begin{equation*} f_{3k+3} = f_{3k+2} + f_{3k+1}\text{.} \end{equation*}

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

\begin{align} f_{3(k+1)} \amp = f_{3k+3}\notag\\ \amp = f_{3k+2} + f_{3k+1}\notag\\ \amp = (f_{3k+1} + f_{3k}) + f_{3k+1}\notag\\ \amp = 2 f_{3k+1} + f_{3k}\tag{19} \end{align}

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

\begin{align*} f_{3(k+1)} \amp = 2 f_{3k+1} + 2m\\ f_{3(k+1)} \amp = 2 (f_{3k+1} + m) \end{align*}

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\text{,}\) the Fibonacci number \(f_{3n}\) is an even natural number.

(c)

Is it true that for each natural number \(n\) with \(n \geq 2\text{,}\) \(f_1 + f_3 + \cdots + f_{2n-1} = f_{n + 1} - 1\text{?}\) Justify your conclusion.

Solution.
Proof.

Let P(n) be ā€œ\(f_1 + f_2 + \cdots + f_{n-1} = f_{n + 1} -1\text{.}\)ā€ Since \(f_1 = f_3 - 1\text{,}\) \(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{equation} f_1 + f_2 + \cdots + f_{k-1} = f_{k + 1} -1\text{,}\tag{20} \end{equation}

and will prove that

\begin{equation} f_1 + f_2 + \cdots + f_{k-1} + f_k = f_{(k + 1) + 1} - 1 = f_{k+2} - 1\text{.}\tag{21} \end{equation}

By adding \(f_k\) to both sides of equation (20), we see that

\begin{align*} (f_1 + f_2 + \cdots + f_{k-1}) + f_k \amp = (f_{k + 1} - 1) + f_k\\ \amp = (f_{k + 1} + f_k) - 1\\ \amp = f_{k + 2} - 1\text{.} \end{align*}

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 \text{,}\) \(f_1 + f_3 + \cdots + f_{2n-1} = f_{n + 1} - 1\)

5.

Prove the following proposition using mathematical induction.

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

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

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 = 3x + 5y\text{.}\)ā€

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

  • \(P(8)\) is true since \(3 \cdot 1 + 5 \cdot 1 = 8\text{.}\)

  • \(P (9)\) is true since \(3 \cdot 3 + 5 \cdot 0 = 9\)

  • \(P (10)\) is true since \(3 \cdot 0 + 5 \cdot 2 = 10\text{.}\)

Inductive Step: Let \(k \in \N\) with \(k \geq 10\text{.}\) Assume that \(P (8)\text{,}\) \(P (9)\text{,}\) ā€¦, \(P (k)\) are true. Now, notice that

\begin{equation*} k + 1 = 3 + (k - 2) \end{equation*}

Since \(k \geq 10\text{,}\) 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 = (3u + 5v)\text{.}\) Using this equation, we see that

\begin{align*} k + 1 \amp = 3 + (3u + 5v)\\ \amp = 3 ( 1 + u) + 5v\text{.} \end{align*}

Hence, we can conclude that \(P (k + 1)\) is true. This proves that if \(P (8)\text{,}\) \(P (9)\text{,}\) ā€¦ , \(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\text{,}\) there exist nonnegative integers \(x\) and \(y\) such that \(n = 3x + 5y\text{.}\)