Show that for all
is a mulitple of 5 using an inductive proof.
I think that I have started this right but I am not sure if it is complete or correct.
So it appears to me that both terms are indeed multiples of 5; however, I thought the original p(n) would be factored out of the equation. In truth, it just looks a little funny. A little help or clarification would be greatly appreciated.
I have several suggestions for making inductive proofs. I don't have the weight of education research methodology behind them, so maybe there are more efficient ways of learning induction. However, these recommendations are easy to follow, and they will keep you from 90% of errors, according to my experience.
1. Distinguish between propositions and numbers. Proposition is a statement that can be either true or false. E.g., "It is raining", "Every even number is divisible by four", "2 + 2 = 5 implies 3 * 0 = 100" (the second is false; the rest are true).
You cannot add propositions using regular numeric addition. The expression True + False is meaningless. On the other hand, numbers cannot be true or false. Thus, is not a proposition; it's a number.
2. Know what a property (or predicate, or relation) is. A property is just like proposition, but it requires a number as input. E.g., can be either true or false depending on ; by itself it is not a proposition. If we denote to be , then the proposition is true and is false. To remind, is meaningless.
Notation: I will write to mean that and are equivalent propositions (both are true or both are false). I prefer using = for numbers and for propositions in order to stress the difference. Also, I will write to mean that is a multiple of 5.
3. Start the proof by identifying the number property that you need to establish for every natural number. This is usually very easy to do because most statements to prove have the form "For all natural , " for some property . So the first thing is to write what is. E.g., in your case the proposition to prove is "For all natural , "; therefore,
Make sure to write the general form of : not or , but for a variable . Also, make sure that (when is unbound) is not a proposition; it is a property that becomes a proposition when is given. Equally important, is not a number. Thus, writing is incorrect.
4. After this, it's easy. Write and prove the base case -- a proposition.
Base case :
5. The induction step consists of proving the following proposition: For all , implies . To prove this, fix an arbitrary and write the assumption, or induction hypothesis (IH), . In this case,
IH: Assume , i.e.,
Next write what we need to prove: . In this case it is:
Need to prove :
(At the risk of being annoying, I remind that and are not numbers. Now that we fixed some concrete , they became propositions.)
The proof was given in the post above. Instead of one should write
By IH, for some natural number ; therefore
, which is a multiple of 5.
(Note that I did not write or in the last two lines because they consists of a chain of equalities of numbers.)
I hope this helps.
Thank you for all the help. I understand it completely. Also, thank you for all of the clarifications. It shed a lot of light on several of my recent doubts.
For others watching this thread I thought it might by helpful to make this step a little more explicit as it confused me a little at first.
The coefficient is broken up in order to factor out .
This is like .