Content
Proof by induction
The concept of a proof by induction with different types of examples.
Want a deeper conceptual understanding? Try our interactive lesson! (Plus Only)
Exercises
No exercises available for this concept.
The concept of a proof by induction with different types of examples.
Want a deeper conceptual understanding? Try our interactive lesson! (Plus Only)
No exercises available for this concept.
We say that an integer a is divisible by b if a=kb for some integer k. In other words ba=k is an integer.
We write "a is divisible by b"
To write "a is not divisible by b" we write
We can prove that an expression is always divisible by some integer D using induction. The easiest way to do this is to subtract the n=k case from the n=k+1 case, and show that the difference is divisible by D.
Induction can be used to prove that an inequality holds. These require very careful "chains" of inequalities.
For example: 2n>n2 for n≥5.
Induction can be used to proved statements involving summations with ∑ . The key is splitting the sum, which has the form
into
and use the inductive hypothesis for r=1∑kf(r).
Induction can be used to prove statements involving the nth derivative of a function. Almost always, the product rule will be the key technique.