mistakes and provide a correct one if possible?
proof for backward induction
Assumption 1: S(n) is true for infintely many natural numbers n
Assumption 2: if S(k) is true-->S(k-1) is also true for k>1
To prove: S(n) is true for all natural number n
Denote a set P(n) which contains some n which S(n) is false
Assume P(n) is not a empty set, i.e. it contains m as its least element
as by Assumption 2 [S(k) is true-->S(k-1) is true] is equivalently equal to
S(k-1) is false-->S(k) is false
so we have P(n) contains infinitely many elements of m, m+1, m+2, m+3....
so for a set S2(n) which contain infintely many natural number, where S(n) is true
is bounded with a upper limit of (m-1)
so we arrive at a contradiction and the assumption of P(n) should have a least
element m is false, i.e. P(n) is a empty set
So, S(n) is true for all natural number N
更新1:
Errr... does this proof has any flaws or logical mistake and which steps (or even the idea) is unneccessary for the proof ?
