Proof by induction - general question - why prove n=1 works?
Hi, so i've started to learn proof by induction, and i know that there are 3 parts to it.
1. show n=1 works
2. assume true for n=k
3. show that n = k+ 1 works
my question is, if we skip the first step (where we prove that n=1 works) and straight away assume true for n=k, and then show that n=k+1 works, then can't we automatically assume n=1 works since in the question it's established that n is any natural number? if thats the case, why do we have to seperately show that n=1 works?
I know it's called a 'base case' but theres no point in proving the base case if we already show that n=k and n= k+1 works
1. show n=1 works
2. assume true for n=k
3. show that n = k+ 1 works
my question is, if we skip the first step (where we prove that n=1 works) and straight away assume true for n=k, and then show that n=k+1 works, then can't we automatically assume n=1 works since in the question it's established that n is any natural number? if thats the case, why do we have to seperately show that n=1 works?
I know it's called a 'base case' but theres no point in proving the base case if we already show that n=k and n= k+1 works
(edited 6 months ago)
Original post by muhammad0112
Hi, so i've started to learn proof by induction, and i know that there are 3 parts to it.
1. show n=1 works
2. assume true for n=k
3. show that n = k+ 1 works
my question is, if we skip the first step (where we prove that n=1 works) and straight away assume true for n=k, and then show that n=k+1 works, then can't we automatically assume n=1 works since in the question it's established that n is any natural number? if thats the case, why do we have to seperately show that n=1 works?
1. show n=1 works
2. assume true for n=k
3. show that n = k+ 1 works
my question is, if we skip the first step (where we prove that n=1 works) and straight away assume true for n=k, and then show that n=k+1 works, then can't we automatically assume n=1 works since in the question it's established that n is any natural number? if thats the case, why do we have to seperately show that n=1 works?
Consider the sequence which is simply the natural numbers, where the next one is one more than the previous. If we miss out the n=1 step, then assume the natural numbers are n+1. So assume true k=n+1, then k+1=n+2 so it works. But it starts at 2 not 1 and every term is wrong by one.
Basically the k->k+1 step shows all the differences are correct. For the differences to correspond to the sequence, the first term must be correct as well.
(edited 6 months ago)
Original post by muhammad0112
Hi, so i've started to learn proof by induction, and i know that there are 3 parts to it.
1. show n=1 works
2. assume true for n=k
3. show that n = k+ 1 works
my question is, if we skip the first step (where we prove that n=1 works) and straight away assume true for n=k, and then show that n=k+1 works, then can't we automatically assume n=1 works since in the question it's established that n is any natural number? if thats the case, why do we have to seperately show that n=1 works?
I know it's called a 'base case' but theres no point in proving the base case if we already show that n=k and n= k+1 works
1. show n=1 works
2. assume true for n=k
3. show that n = k+ 1 works
my question is, if we skip the first step (where we prove that n=1 works) and straight away assume true for n=k, and then show that n=k+1 works, then can't we automatically assume n=1 works since in the question it's established that n is any natural number? if thats the case, why do we have to seperately show that n=1 works?
I know it's called a 'base case' but theres no point in proving the base case if we already show that n=k and n= k+1 works
In the inductive step, one shows that n = k + 1 works provided that n = k works. This is basically showing that if something holds for an arbitrary n, then we can go one step further and make it also hold for the next natural number. So in particular, we can reach the conclusion we want (the claimed statement being true for any natural number n) by iteratively going up one step at a time. E.g. if we want to show some statement is true for n = 3 and we know that "taking one step up at a time" works, then we just start from 1, go to 2 then finally to 3. The base case is what makes this process of "going up by 1 at a time" possible because you must start somewhere, with a statement that holds true.
Note, you can show the base case for different natural numbers, does not have to be 1. Then the conclusion will hold for all integers >= the one you started for the base case.
(edited 6 months ago)
Another, perhaps more anecdotal than maths, perspective.
If you've come across the metaphor "induction is like dominoes", showing "P(k+1) is true assuming P(k) is true" is like you've built the perfectly aligned domino line. But no one will be convinced your domino line actually works until everything gets toppled. Showing a base case is true is to actually initiate the toppling sequence somewhere - usually from the beginning (i.e. P(1) is true).
Now perhaps less anecdotal, but still not quite mathy example (mostly it's not really well-posed, but meh).
Suppose you want to show that all horses in the world have the same color. Well, the induction step starts by assuming if you have k horses, they will have the same color. Then in the k+1 case, the first k horses have the same color by assumption, and the last k horses also have the same color by assumption, so all k+1 horses do have the same color... The induction step is perfectly fine, but our base case is not true (e.g. n=2 obviously fails).
Sidenote: Obviously all the base case check you do in A-Levels are painfully trivial. But apparently there are loads of problems out there where the induction step is actually the easy stuff, and the base case check is the actual hard stuff. God knows what the problems are - I'm not that good at maths yet.
If you've come across the metaphor "induction is like dominoes", showing "P(k+1) is true assuming P(k) is true" is like you've built the perfectly aligned domino line. But no one will be convinced your domino line actually works until everything gets toppled. Showing a base case is true is to actually initiate the toppling sequence somewhere - usually from the beginning (i.e. P(1) is true).
Now perhaps less anecdotal, but still not quite mathy example (mostly it's not really well-posed, but meh).
Suppose you want to show that all horses in the world have the same color. Well, the induction step starts by assuming if you have k horses, they will have the same color. Then in the k+1 case, the first k horses have the same color by assumption, and the last k horses also have the same color by assumption, so all k+1 horses do have the same color... The induction step is perfectly fine, but our base case is not true (e.g. n=2 obviously fails).
Sidenote: Obviously all the base case check you do in A-Levels are painfully trivial. But apparently there are loads of problems out there where the induction step is actually the easy stuff, and the base case check is the actual hard stuff. God knows what the problems are - I'm not that good at maths yet.
(edited 6 months ago)
Original post by tonyiptony
... apparently there are loads of problems out there where the induction step is actually the easy stuff, and the base case check is the actual hard stuff. God knows what the problems are - I'm not that good at maths yet.
One nice one is the McNugget problem:
"McNuggets can be bought in boxes of 6, 9 and 20. Show that you can always buy exactly N McNuggets if N>43".
Proof: "base case is to exhibit solutions for N=44 through N=49", induction (in steps of 6) is just "add a box of 6 nuggets".
Another one (that's not quite induction but has a very similar feel): given one non-trivial integer solution to x^2 - ky^2=1, it's fairly straightforward to find an infinite number of solutions. But it's non-trivial to find that first solution.
Quick Reply
Related discussions
- Recursion Q
- Question on proof by induction for Inductive Sequences
- Proving a fraction involving infinity tends to 0
- BMO 1993, Round 1, Question 3
- Bmo 2023/24
- Oxbridge Maths - Interview Questions
- Core pure maths Series question
- Algebra help for proof by induction
- Math Proof Questions
- How do I use proof by induction on this, specifically using f(k+1)-f(k)?
- STEP foundation module help pls
- Proof by induction question
- BMO1 questions
- STEP I, II, III 1999 solutions
- Construct a recursive formula and prove using induction
- AQA A-Level Maths 2021 Paper 1 Question (13c)
- A-level Edexcel Maths - Proofs
- AQA A-level Further Mathematics Paper 2 (7367/2) - 5th June 2023 [Exam Chat]
- Core Pure AS Maths: series question
- Edexcel AS Level Further Maths 2022
Latest
Trending
Last reply 4 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
Trending
Last reply 4 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
