What is proof by induction?

• Proof by induction?is a way of proving a?result is true for a set of integers?by showing that if it is?true for one integer then it is true for the next integer
• It can be thought of as dominoes:
  • All dominoes will fall down if:
    • The first domino falls down
    • Each domino falling down causes the next domino to fall down

What are the steps for proof by induction?

• STEP 4: The conclusion step
  • State?the result is true
  • Explain in words?why the result is true
  • It must include:
    • If true for?n?=?k?then it is true for?n?=?k?+ 1
    • Since true for?n?= 1 the statement is true for all?n?∈ ?,?n?≥ 1 ?by mathematical induction
  • The sentence will be the same for each proof just change the base case from?n?= 1 if necessary

What type of statements might I be asked to prove by induction?