http://www.ck12.org Chapter 12. Discrete Math
Rewrite the right side: 1+ 2 + 3 + 4 +···+k+(k+ 1 ) =(k+^1 )(( 2 k+^1 )+^1 )
∴
Practice
For each of the following statements: a) show the base case is true; b) state the inductive hypothesis; c) state what
you are trying to prove in the inductive step/proof.Do not prove yet.
- Forn≥ 5 , 4 n< 2 n.
- Forn≥ 1 , 8 n− 3 nis divisible by 5.
- Forn≥ 1 , 7 n−1 is divisible by 6.
- Forn≥ 2 ,n^2 ≥ 2 n.
- Forn≥ 1 , 4 n+5 is divisible by 3.
- Forn≥ 1 , 02 + 12 +···+n^2 =n(n+^1 )( 62 n+^1 )
Now, prove each of the following statements. Use your answers to problems 1-6 to help you get started. - Forn≥ 5 , 4 n< 2 n.
- Forn≥ 1 , 8 n− 3 nis divisible by 5.
- Forn≥ 1 , 7 n−1 is divisible by 6.
- Forn≥ 2 ,n^2 ≥ 2 n.
- Forn≥ 1 , 4 n+5 is divisible by 3.
- Forn≥ 1 , 02 + 12 +···+n^2 =n(n+^1 )( 62 n+^1 )
- You should believe that the following statement is clearly false. What happens when you try to prove it true by
induction?
Forn≥ 2 ,n^2 <n - Explain why the base case is necessary for proving by induction.
- The principles of inductive proof can be used for other proofs besides proofs about numbers. Can you prove the
following statement from geometry using induction?
The sum of the interior angles of any n−gon is 180 (n− 2 )for n≥3.
You learned that recursion, how most people intuitively see patterns, is where each term in a sequence is defined
by the term that came before. You saw that terms in a pattern can also be represented as a function of their term
number. You learned about two special types of patterns called arithmetic sequences and geometric sequences that
have a wide variety of applications in the real world. You saw that series are when terms in a sequence are added
together. A strong understanding of patterns helped you to count efficiently, which in turn allowed you to compute
both basic and compound probabilities. Finally, you learned that induction is a method of proof that allows you to
prove your own mathematical statements.