Mathematical induction数学的帰納法すうがくてききのうほう and recursive definitions再帰的定義さいきてきていぎ

document_iddoc_a41fb04c8a81d120d4afb0e833266e9etitle数学的帰納法と再帰的定義講義type講義content_typelecturedate2026-07-14categorymathdescription自然数上の命題を扱う数学的帰納法と、数列・木・グラフの定義に現れる再帰的定義を説明する。prerequisites命題・述語と量化 / 証明法と反例 / 集合の基本 / べき集合の基本 / 集合の濃度と可算性

In discrete mathematics離散数学りさんすうがく, arguments often add objects one by one. Mathematical induction数学的帰納法すうがくてききのうほう turns the structure "it holds at the start, and if it can advance to the next case, then it holds everywhere" into a proof method.

Mathematical induction数学的帰納法すうがくてききのうほう is a proof method that extends a proposition along the natural numbers自然数しぜんすう. A recursive definition再帰的定義さいきてきていぎ gives base objects and rules for constructing new objects from ones already built.

1Induction form

Suppose we want to prove a proposition命題めいだい $P (n)$ about a natural number自然数しぜんすう $n$ for all $n [PARSE ERROR: Undefined("Command(\"ge\")")] n_{0}$ . Then we prove the following two statements.

P (n_{0})

P (k) \Rightarrow P (k + 1) (k [PARSE ERROR: Undefined("Command(\"ge\")")] n_{0})

The first statement is the base case基底段階きていだんかい, and the second statement is the induction step帰納段階きのうだんかい. The temporary assumption $P (k)$ used inside the induction step is the induction hypothesis帰納法の仮定.

Both the base case基底段階きていだんかい and the induction step帰納段階きのうだんかい are necessary. Checking several examples does not prove all $n$ ; the proof needs a logical step that derives $P (n + 1)$ from the assumption $P (n)$ .

2Why it works

Mathematical induction数学的帰納法すうがくてききのうほう can be understood through the domino metaphor. The base case基底段階きていだんかい says that the first domino falls. The induction step帰納段階きのうだんかい says that whenever an arbitrary domino falls, the next one also falls. Therefore every domino falls.

For a rigorous view, use the well-ordering property整列性せいれつせい: every nonempty subset of the natural numbers has a least element. Suppose the set of $n [PARSE ERROR: Undefined("Command(\"ge\")")] n_{0}$ for which $P (n)$ fails were nonempty, and let $m$ be its least element. Since $P (n_{0})$ is true, $m > n_{0}$ . Minimality gives $P (m - 1)$ , and the induction step then gives $P (m)$ , contradicting the choice of $m$ .

The base case基底段階きていだんかい gives the first reachable point, and the induction step帰納段階きのうだんかい gives the rule for moving one step forward. Repeating this rule finitely many times reaches any chosen natural number自然数しぜんすう.

3Worked theorem: size of a power set

We now use the power sets[べき集合] and cardinality developed in the preceding lectures. Here, $| A |$ is the number of elements元げん of $A$ , and $[PARSE ERROR: Undefined("Command(\"mathcal\")")] P (A)$ is the set集合しゅうごう of all subsets部分集合ぶぶんしゅうごう of $A$ .

Let $P (n)$ mean “for every set $A$ with $n$ elements, $| [PARSE ERROR: Undefined("Command(\"mathcal\")")] P (A) | = 2^{n}$ .” We prove $P (n)$ for every $n [PARSE ERROR: Undefined("Command(\"ge\")")] 0$ .

As the base case基底段階きていだんかい, when $n = 0$ we have $A = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ and

[PARSE ERROR: Undefined("Command(\"mathcal\")")] P ([PARSE ERROR: Undefined("Command(\"varnothing\")")]) = {[PARSE ERROR: Undefined("Command(\"varnothing\")")]},

so $| [PARSE ERROR: Undefined("Command(\"mathcal\")")] P (A) | = 1 = 2^{0}$ . It is important to state the case $n = 0$ explicitly. The empty set is not an exception; it is the starting point of the formula.

For the induction step帰納段階きのうだんかい, assume $P (k)$ and take an arbitrary set $A^{'}$ with $k + 1$ elements. Choose $a \in A^{'}$ and put $A = A^{'} ∖ {a}$ , so $| A | = k$ . Each subset部分集合ぶぶんしゅうごう of $A^{'}$ either does not contain $a$ or does contain $a$ . The subsets not containing $a$ are exactly the subsets of $A$ , and the subsets containing $a$ correspond one-to-one to sets of the form $B \cup {a}$ with $B \subseteq A$ . Therefore

| [PARSE ERROR: Undefined("Command(\"mathcal\")")] P (A^{'}) | = 2^{k} + 2^{k} = 2^{k + 1} .

data/lecture/math/discrete-math/power-set-basics.lecture.n.md data/lecture/math/discrete-math/cardinality-and-countability.lecture.n.md

4Recursive definitions

A recursive definition再帰的定義さいきてきていぎ gives base objects and rules for constructing new objects from ones already defined. For a sequence this produces a next term; for a tree or logical formula it combines smaller structures into a larger one. For example,

a_{0} = 1, a_{n + 1} = 2 a_{n} + 1

Specifying $a_{0}$ is necessary; the rule for producing the next term alone does not determine the values.

For a recursive definition再帰的定義さいきてきていぎ, always check the following points.

Base values or base objects are specified.
Rules for constructing new objects from previously constructed ones are clear.
For a sequence, the range of $n$ is clear; for a structure, the permitted constructors are clear.

For a recursive definition再帰的定義さいきてきていぎ, check that neither the base objects nor the construction rules are missing. Uniqueness from the same bases and rules can be proved by mathematical induction数学的帰納法すうがくてききのうほう for sequences, and by induction following the construction for trees or logical formulas.

5Warning

The induction hypothesis is not the statement to be proved for all $n$ at once. It is a temporary assumption for one arbitrary $k$ , used only to prove the next case.

7Exercise links

data/exercise/math/discrete-math/logic-and-proof-methods.exercise.n.md

8Summary

Mathematical induction数学的帰納法すうがくてききのうほう is a basic proof method for statements over the natural numbers自然数しぜんすう. Recursive definitions再帰的定義さいきてきていぎ are used frequently when defining sequences, trees, graphs, and computational procedures.