Is this proof valid? Strong Induction

Question

Suppose a recursively defined sequence $f_n = f_{n-1} + f_{n-2}$ where f(1) = 1 and f(2) = 3

Then, let P(n) denote $f_n < (7/4)^n \space \space \space\forall n\in \mathbb{Z^+}$

1 < 7/4, P(1) is true 3 < 343/64, P(2) is true

Assume P(i) is true $\forall i\in\mathbb{Z^+}, s.t 1\le i \le k$

Now to prove P(k+1)

$f_{k+1} < (7/4)^{k+1}$

$f_{k} + f_{k-1} < (7/4)^{k+1}$ (Substitution with recurrence relation)

$(7/4)^k + 7/4^{k-1} < (7/4)^k * 7/4$ (Substitution with previous assumption)

$(7/4)^{k-1} + (7/4)^{k-2} < (7/4)^k$ (division by 7/4)

$(7/4)^k * (4/7+16/49) < (7/4)^k$ (Rewriting LHS)

$44/49 < 1$ (Cancelation of $(7/4)^k$ and addition of the terms inside the backets)

$\therefore$ P(k+1) is true whenever P(i) is true $\forall i\in\mathbb{Z^+}$, s.t $1 \le i \le k$ and since P(1) and P(2) are true, by strong induction we have that P(n) is true $\forall n\in\mathbb{Z^+}$

Q.E.D

I don't know whether this proof is right, because it seems like cheating (even though I don't believe I used any circular reasoning or made the assumption that $f_{n+1}<(7/4)^k$ right away, so it seems right, but I am still skeptical as when following a youtube video, the person within did it in a different way, if anyone could point out any mistakes if there are any please do so.)

Answer 1

The proof is valid, but I only realized this after trying to reconstruct what your logic is -- so although it is correct, I would criticize the clarity of writing.

For one thing, you don't say what $f(1)$ or $f(2)$ are, although from what you write elsewhere I think that I infer that these are supposed to be 1 and 3 respectively.

My first really significant criticism is the sequence

$$ f_{k+1} < (7/4)^{k+1} $$

$$ f_k+f_{k-1} < (7/4)^k (7/4) $$

$$ (7/4)^k + (7/4)^{k-1} < (7/4)^k (7/4) $$

It is not clear what is happening from one line to the next. This is especially a problem here, because the move taking you from the first to the second line, is importantly different from the kind of move that takes you from the second to the third.

The move from the first to the second is merely a substitution of equals and therefore this is completely valid -- but good proof-writing would tell the reader that this is what you're doing.

The move from the second to the third looks like a substitution of unequals, and therefore causes concern since that is not always valid.

However, after trying to see how you're using these sentences, I realize that you're not merely substituting unequals. Or if you are, then you got lucky, because there is a way to put these sentences together to form a valid argument -- but it's not exactly by substituting unequals.

If you were saying

"We are trying to prove $ f_k+f_{k-1} < (7/4)^k (7/4) $, but because we know $f_k+f_{k-1} < (7/4)^k+(7/4)^{k-1}$, then it suffices if we prove that $(7/4)^k+(7/4)^{k-1} < (7/4)^k(7/4)$".

then the logic would be clearer. And indeed this is a valid argument, and from here everything that you write is equivalent to this. So it is a valid argument.