Understanding Proof by Induction

[fathom drift]

I find that these proofs are getting a little bit out of hand in terms of making sense.. let me explain:

Proposition: If a tree has n vertices, then it has n−1 edges
So that's the proposition, that's what we're trying to prove, and the book does so via induction.

Suppose that for each m with 1 ≤ m ≤ k, any tree with m vertices has m−1 edges
This is our inductive hypothesis, we assume this to be true.. um.. okay.

our inductive hypothesis guarantees that T1 has x−1 edges, and T2 has y−1 edges.
Now this is where everything starts falling apart, because what just happened after this is that we just proved our proposition via some assumption/hypothesis.

'Our hypothesis guarantees that...', whaa? So I can just run around hypothesizing things and they automatically become true? This has got to be some load of nonsense right?

[tight widget]

ah it's from the book of proof

the way you're speaking about induction really sounds like someone who hasn't seen an induction proof in their life before (even though there's a whole section devoted to basic induction before that)

induction isn't just hypothesizing whatever the hell we want and be done with it

it's a very specific pattern of
(1) base case
(2) induction step
carefully chosen so that when you combine the two, you prove a statement for all integers

there's no random hypothesizing, it's done with intent to prove the statement

do you still have issues with the first section about "normal" induction ? (cause your "random hypothesizing" shtick also applies there), or is it just this specific induction question you have problems with ?

[fathom drift]

Oh yeah, I already went thru the previous normal induction section

And I kinda just accepted that you hypothesize about things

But then when I came to the proposition screenshotted above, that's when I was like, "Yeah okay, it's getting pretty ridiculous just hypothesizing things and bada bing bada boom, a proof comes out on the other side"

[tight widget]

yea, strong induction on graphs when the book introduces graphs just before can be unsettling

induction shows up in a lot of places and is pretty f-ing powerful, there's a reason it's taught in intro to proof books

you could try working through the natural number game https://adam.math.hhu.de/#/g/leanprover-community/nng4, it's an intro to lean, a proof assistant/checker
a ton of stuff is defined by recursion in lean (natural numbers in particular), so most proofs in there involve induction, it's a nice training ground