An induction proof

[lament raptor]

In this proof, I am assuming the relation is true at n-1 and wanna prove it at n. But, I do not have a definition for n-2. Can I just assume that the relation is also true at n-2? What's the reasoning on it if yes

[wispy pendant]

Yes you can assume that the relationship is true at every inferior level.

If you're not convinced you can replace the induction hypothesis with "for every k from 1 to n, the relation holds"

but specifically here you have 2 base cases

it's P(1), P(2) and P(n-2) and P(n-1) => P(n)

[lament raptor]

Yeah I realised that for the assumption to hold true for some specific k, it has to hold true for every number upto k anyways bcoz the definition is recursive. Or else, I'll just end up going back in loops of definition from k to k-1 to k-2 and end at the base case again.

[wispy pendant]

FYI recursion is far more general than that, it can be generalized on well-founded spaces, i.e. (to simplify) ordered sets with no infinite strictly decreasing sequences

[lament raptor]

I do not understand a single thing in that

xD

[wispy pendant]

not important

[lament raptor]

Alright

Thanks for the help

[wispy pendant]

lemme give an example

imagine N², the set of couples of natural numbers

[lament raptor]

Hmm

[wispy pendant]

wait I have a better idea

[lament raptor]

Okay

[wispy pendant]

Let Σ* be the set of words (not just English words, any combination of letters)

You have a natural ordering on this set of words, for example aa < ab

[lament raptor]

Gotchu

[wispy pendant]

You can perform induction on this set, the base case would be "a" or the empty word, depending on your definition

[lament raptor]

Okay

[wispy pendant]

This is more general

[lament raptor]

I get the idea of base definition

I was confused on the idea of how it gets defined for terms lower than k, where we are trying to prove for k+1 using k as our case

But that's just the definition of mathematical induction, where you know it's true for k bcoz it's true for k-1

Right?

[wispy pendant]

Let me just write it properly

[lament raptor]

Okay

[wispy pendant]

Let P(n) a property.

Induction principle states : if P(0) holds and for any natural number n (including 0), if P(n) holds then P(n+1) holds THEN P(n) holds for any n.

[lament raptor]

Yeah gotchu

[wispy pendant]

Let H(n) = "for k=0 to n P(k) holds"

it can be proven by basic induction

wait this is stupid

[lament raptor]

I am not sure how to prove it

Oh wait

Wait but you're proving induction using induction

[wispy pendant]

well there are different kinds of induction

[lament raptor]

I only know one T-T

[wispy pendant]

• when you prove P(0) and $\forall n \in \bN P(n) \Rightarrow P(n+1)$ \
• when you prove P(0) and $\forall n \in \bN (\forall k < n, P(k) \Rightarrow P(n))$ \
• when you prove P(0) and P(1) and $\forall n \in \bN, (P(n) \wedge P(n+1)) \Rightarrow P(n+2)$

[merry shell]

Valentin

[wispy pendant]

but they are all the same fundamentally

[lament raptor]

Yeah that's what I was thinking

[wispy pendant]

It's a good exercise to deduce the two last ones from the first one

And you can also prove the first ! (from other axioms of course) :

Let P a property such that P(0) holds and forall n, P(n) => P(n+1).

Assume by contradiction there exists a N such that (not P(N)) holds.
Let A = {n in N | not P(n)}.
As it's a subset of N and is non-empty (has N), it has a minimum m. This minimum is not 0 as P(0) holds. However not P(m) holds then not P(m-1) holds, then m-1 is in A, therefore it contradicts the fact that m is the minimum of A.

[lament raptor]

Omgg

[wispy pendant]

yes it's great

[lament raptor]

I love IT

[wispy pendant]

you're welcome !

[lament raptor]

Thanks, you just made my day better xD

[wispy pendant]

What class are you in ?

[lament raptor]

Completed high school, transitioning to uni

[wispy pendant]

Wish you all the best

[lament raptor]

Thank you so much

[lament raptor]

.close