csat-suneung 2006 Q16

csat-suneung · South-Korea · csat__math-science 4 marks Proof by induction Fill in missing steps of a given induction proof
The following is a proof by mathematical induction that for all natural numbers $n$,
$$\sum _ { k = 1 } ^ { n } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { n } \right) = \frac { n ( 5 n + 3 ) } { 4 }$$
holds.

(1) When $n = 1$, (left side) $= 2$, (right side) $= 2$, so the given equation holds.
(2) Assume that the equation holds when $n = m$:
$$\begin{aligned} & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { m } \right) \\ = & \frac { m ( 5 m + 3 ) } { 4 } \end{aligned}$$
Now we show that it holds when $n = m + 1$.
$$\begin{aligned} & \sum _ { k = 1 } ^ { m + 1 } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) \\ = & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) + \frac { \text { (가) } } { m + 1 } \\ = & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { \sqrt { \text { (나) } } } \right) \\ \quad & \quad + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) + \frac { \text { (가) } } { m + 1 } \\ = & \frac { m ( 5 m + 3 ) } { 4 } + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m + 1 } \text { (다) } \\ = & \frac { ( m + 1 ) ( 5 m + 8 ) } { 4 } \end{aligned}$$
Therefore, the equation also holds when $n = m + 1$. Thus, the given equation holds for all natural numbers $n$.
What should be filled in for (가), (나), and (다) in the above proof? [4 points]
(가)(나)(다)
(1)$5 m - 3$$m$$5 k + 2$
(2)$5 m - 3$$m + 1$$5 k + 2$
(3)$5 m + 2$$m$$5 k - 3$
(4)$5 m + 2$$m$$5 k + 2$
(5)$5 m + 2$$m + 1$$5 k - 3$
The following is a proof by mathematical induction that for all natural numbers $n$,

$$\sum _ { k = 1 } ^ { n } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { n } \right) = \frac { n ( 5 n + 3 ) } { 4 }$$

holds.

<Proof>

(1) When $n = 1$, (left side) $= 2$, (right side) $= 2$, so the given equation holds.

(2) Assume that the equation holds when $n = m$:

$$\begin{aligned}
& \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \frac { 1 } { k + 2 } + \cdots + \frac { 1 } { m } \right) \\
= & \frac { m ( 5 m + 3 ) } { 4 }
\end{aligned}$$

Now we show that it holds when $n = m + 1$.

$$\begin{aligned}
& \sum _ { k = 1 } ^ { m + 1 } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) \\
= & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { m + 1 } \right) + \frac { \text { (가) } } { m + 1 } \\
= & \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) \left( \frac { 1 } { k } + \frac { 1 } { k + 1 } + \cdots + \frac { 1 } { \sqrt { \text { (나) } } } \right) \\
\quad & \quad + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m } ( 5 k - 3 ) + \frac { \text { (가) } } { m + 1 } \\
= & \frac { m ( 5 m + 3 ) } { 4 } + \frac { 1 } { m + 1 } \sum _ { k = 1 } ^ { m + 1 } \text { (다) } \\
= & \frac { ( m + 1 ) ( 5 m + 8 ) } { 4 }
\end{aligned}$$

Therefore, the equation also holds when $n = m + 1$.\\
Thus, the given equation holds for all natural numbers $n$.

What should be filled in for (가), (나), and (다) in the above proof? [4 points]

\begin{center}
\begin{tabular}{ c c c c }
 & (가) & (나) & (다) \\
(1) & $5 m - 3$ & $m$ & $5 k + 2$ \\
(2) & $5 m - 3$ & $m + 1$ & $5 k + 2$ \\
(3) & $5 m + 2$ & $m$ & $5 k - 3$ \\
(4) & $5 m + 2$ & $m$ & $5 k + 2$ \\
(5) & $5 m + 2$ & $m + 1$ & $5 k - 3$ \\
\end{tabular}
\end{center}