kidzsearch.com > wiki Explore:




Mathematical induction
Mathematical induction is a special way of proving a mathematical truth. It can be used to prove that something is true for all the natural numbers (or all positive numbers from a point onwards).[1][2] The idea is that if:
- Something is true for the first case (base case);
- Whenever that same thing is true for a case, it will be true for the next case (inductive case),
then
- That same thing is true for every case by induction.[3]
In the careful language of mathematics, a proof by induction often proceeds as follows:
- State that the proof will be by induction over [math]n[/math]. ([math]n[/math] is the induction variable.)
- Show that the statement is true when [math]n[/math] is 1.
- Assume that the statement is true for any natural number [math]n[/math]. (This is called the induction step.)
- Show then that the statement is true for the next number, [math]n+1[/math].
Because it is true for 1, then it is true for 1+1 (=2, by the induction step), then it is true for 2+1 (=3), then it is true for 3+1 (=4), and so on.
An example of proof by induction is the following:
Prove that for all natural numbers n:
- [math]1+2+3+....+(n-1)+n=\tfrac12 n(n+1)[/math]
Proof:
First, the statement can be written as:
- [math]2\sum_{k=1}^n k=n(n+1)[/math] (for all natural numbers n)
By induction on n,
First, for n=1:
- [math]2\sum_{k=1}^1 k=2(1)=1(1+1)[/math],
so this is true.
Next, assume that for some n=n0 the statement is true. That is,:
- [math]2\sum_{k=1}^{n_0} k = n_0(n_0+1)[/math]
Then for n=n0+1:
- [math]2\sum_{k=1}^{{n_0}+1} k[/math]
can be rewritten as
- [math]2\left( \sum_{k=1}^{n_0} k+(n_0+1) \right) [/math]
Since [math]2\sum_{k=1}^{n_0} k = n_0(n_0+1),[/math]
- [math]2\sum_{k=1}^{n_0+1} k = n_0(n_0+1)+2(n_0+1) =(n_0+1)(n_0+2)[/math]
Hence the proof is complete by induction.
Similar proofs
Mathematical induction is often stated with the starting value 0 (rather than 1). In fact, it will work just as well with a variety of starting values. Here is an example when the starting value is 3: "The sum of the interior angles of a [math]n[/math]-sided polygon is [math](n-2)180[/math] degrees."
The initial starting value is 3, and the interior angles of a triangle is [math](3-2)180[/math] degrees. Assume that the interior angles of a [math]n[/math]-sided polygon is [math](n-2)180[/math] degrees. Add on a triangle which makes the figure a [math]n+1[/math]-sided polygon, and that increases the count of the angles by 180 degrees [math](n-2)180+180=(n+1-2)180[/math] degrees. Since both the base case and the inductive case are handled, the proof is now complete.
There are a great many mathematical objects for which proofs by mathematical induction works. The technical term is a well-ordered set.
Inductive definition
The same idea can work to define a set of objects, as well as to prove statements about that set of objects.
For example, we can define [math]n[/math]th degree cousin as follows:
- A [math]1[/math]st degree cousin is the child of a parent's sibling.
- A [math]n+1[/math]st degree cousin is the child of a parent's [math]n[/math]th degree cousin.
There is a set of axioms for the arithmetic of the natural numbers which is based on mathematical induction. This is called "Peano's Axioms". The undefined symbols are | and =. The axioms are
- | is a natural number.
- If [math]n[/math] is a natural number, then [math]n|[/math] is a natural number.
- If [math]n| = m|[/math] then [math]n = m[/math].
One can then define the operations of addition and multiplication and so on by mathematical induction. For example:
- [math]m + | = m|[/math]
- [math]m + n| = (m + n)|[/math]
Related pages
References
- ↑ "The Definitive Glossary of Higher Mathematical Jargon" (in en-US). 2019-08-01. https://mathvault.ca/math-glossary/.
- ↑ "3.4: Mathematical Induction - An Introduction" (in en). 2018-04-25. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Book%3A_A_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)/03%3A_Proof_Techniques/3.04%3A_Mathematical_Induction_-_An_Introduction.
- ↑ "Induction". http://discrete.openmathbooks.org/dmoi2/sec_seq-induction.html.
|
|