수학적 귀납법 연습문제 — Sundstrom, Mathematical Reasoning · 4.2절 · 12번

Sundstrom, Mathematical Reasoning · 4.2절 · 12번영어 원문

Prove that for each natural number $n$ , any set with $n$ elements has $\dfrac{n \left( {n-1} \right)}{2}$ two-element subsets.

정답·풀이 보기 (영어 원문)

Let $P ( n )$ be, “Any set with $n$ elements has $\dfrac{n ( n - 1 )}{2}$ 2-element subsets.” $P ( 1 )$ is true since any set with only one element has no 2-element subsets. Let $k \in \mathbb{N}$ and assume that $P ( k )$ is true. This means that any set with $k$ elements has $\dfrac{k ( k - 1 )}{2}$ 2-element subsets. Let $A$ be a set with $k + 1$ elements, and let $x \in A$ . Now use the inductive hypothesis on the set $A - \left\{ x \right\}$ , and determine how the 2-element subsets of $A$ are related to the set $A - \left\{ x \right\}$ .

한 번 더 — 비슷한 문제Sundstrom, Mathematical Reasoning · 4.1절 · 3a번영어 원문

Use mathematical induction to prove each of the following:

For each natural number $n$ , $2 + 5 + 8 + \cdots + \left( {3n - 1} \right) = \dfrac{{n\left( {3n + 1} \right)}}{2}$ .

다 풀었으면 정답 확인

For each $n \in \mathbb{N}$ , let $P( n )$ be, $2 + 5 + 8 + \cdots + (3n - 1) = \dfrac{{n( {3n + 1} )}}{2}$ . When we use $n = 1$ , the summation on the left side of the equation is 2, and the right side is $\dfrac{1(3 \cdot 1 + 1)}{2} = 2$ . Therefore, $P( 1 )$ is true. For the inductive step, let $k \in \mathbb{N}$ and assume that $P \left( k \right)$ is true. Then,

$2 + 5 + 8 + \cdots + \left( {3k - 1} \right) = \frac{{k \left( {3k + 1} \right)}}{2}$

. We now add $3 \left( k + 1 \right) - 1$ to both sides of this equation. This gives

$\begin{aligned}2 + 5 + 8 + \cdots + (3k - 1) & \\ + 3 \left( {k + 1} \right)-1 & = \frac{{k \left( {3k + 1} \right)}}{2} + \left( 3 \left( k + 1 \right) - 1 \right) \\ & = \frac{{k \left( {3k + 1} \right)}}{2} + \left( {3k + 2} \right)\end{aligned}$

If we now combine the terms on the right side of the equation into a single fraction, we obtain

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

This proves that if $P\left( k \right)$ is true, then $P\left( {k + 1} \right)$ is true.

이 문제로 이어서 풀기

# 수학적 귀납법증명·논술자동 분류