Setting up a Problem for Induction that Involves Inequality and a Function

Question

The problem states:

Use mathematical induction to prove that any stack of ($n\geq 5$) pancakes can be  sorted using at most $2n-5$ flips.  You may use the fact  any stack of $5$ pancakes can be  sorted with at most $5$ flips

I am trying to set it up for induction but I am having trouble doing so.

So far I have done this:

$F(n)\leq 2n-5$

Where F is the function to represent the number of flips at most to sort $n$ number of pancakes.

From there I got to the Base Case(note the problem supplied a possible base case that I am using here):

$F(5)\leq 2\cdot 5-5$

$5\leq 5$ is True.

Using this base case say that $n=5$ is represented as $k$. I need to prove that $k+1$ will also be valid. This is where I get stuck and I wonder if its an issue with how I tried to capture the question mathematically. Does anyone have any suggestions on how to better approach it. I'm very new to all this.

Scratch Work that leads to my stump:

$$F(k + 1) \leq 2(k + 1) -5$$

$$F(k + 1) \leq 2k -3$$

Not sure how to work with this in a way that would tell me anything useful. Thanks in Advance.

Answer 1

If $F(n)$ denotes the number of flips required to sort $n$ pancakes then you want to show that the statement $$ S(n): F(n) \le 2n - 5 $$ is true for $n \ge 5$.

The base case is $S(5): F(5) \le 2\cdot 5 - 5 = 5$ and that is given.

Now you have to show that for all $n \ge 5$: $S(n) \Longrightarrow S(n+1)$, in other words, $$ F(n) \le 2n-5 \Longrightarrow F(n+1) \le 2(n+1) - 5 $$ and that follows from the observation (taken from https://oeis.org/A058986):

If the worst case for n pancakes is x flips, then the worst case for n + 1 pancakes can be no greater than x + 2 flips. Getting the n + 1 pancake to the bottom of the pile will require 0, 1 or 2 flips, after which you can sort the n remaining pancakes in at most x flips.

which implies that $F(n+1) \le F(n) + 2$.