Uni Mathematical Proofs (Just part A & D)

[maiden wren]

How many base cases would I need for both parts?? My gut tells me two but my notes just tell me one (n=0) (this is wanting proof by strong induction btw)

[opaque acorn]

Why does your gut feel like two base cases are needed?

[maiden wren]

I think its the n+2 throwing me off a bit

[opaque acorn]

If your induction step looked like P(n) -> P(n+2), then you would need to cover the base case for n=0 and n=1, because the "induction dominoes" would be set up in two different lines: in that last example, they would just be the even and odd numbers.

For your problem, your induction step need not look like that. The statements are in terms of one variable and don't need to skip a step. For (a), you can just show n=0 and then move to the strong induction step where you assume P(0), P(1), ... P(n) and use them to prove P(n+1). This is fine because in the strong induction domino sequence P(0) is all you need to show P(1), P(0) and P(1) is all you need to show P(2), and so on.

[maiden wren]

Is that because with fibonacci, generally anything P(0) and up is kind of given? (Hopefully I’m trying to convey that thought correctly)

Or- if I’m understanding what you’re saying correctly, because we’re literally gunning just for P(n) using P(n+2)

[opaque acorn]

It's just true in general for induction, not using any specific property of the Fibonacci numbers.
In the second paragraph above, I'm attempting to show that just because we assume every P up to P(n) doesn't mean we need more base cases. If the strong induction step works out, then P(1) and P(2) are all taken care of without need for base cases.

As for the F_{n+2} in part (a), this doesn't impact the fact that the whole equation there is a predicate in terms of n that we'll call P(n). We aren't skipping any steps like in my P(n) -> P(n+2) example: for n=0, the RHS will be F{2} - 1, for n=1, it'll be F{3} - 1.

[opaque acorn]

So no it doesn't have to do with the fact that we're working on a sequence that uses 2 previous terms instead of 1 or 0

[maiden wren]

I’ll definitely have to simmer on this for a bit and re-read to fully understand. But meanwhile, thank you! I do appreciate the help!

[opaque acorn]

I know the feel, I hope my explanation made things clearer at least a bit have fun!