Proof by strong induction

Question

$F(0) = 0$

$F(1) = 0$

$F(n) = 1 + F(n-2)$ , when $n > 1$

Prove by strong induction that $F(n)=n$ div $2$ for $n\geq0$

$a$ div $b$ is a integer division. So $10$ div $2 = 5$, $11$ div $2 = 5$, $12$ div $2=6$ and so on.

Did the base cases and they hold? Got stuck in the stepcase. I don't know if I am doing it right. This is what I have done so far.

$F(n+1)= 1 + F(n+1-2)$

$F(n+1) = (n+1)$ div $2$

$1 + (n+1)$ div $2 - 2= n$ div $2$

Which we had to prove

Have another idea.

$F(n+1) = 1 + F(n+1 -2)$

$F(n+1-2) = F(n) (I.H) k>1$

$1+F(n) = 1+n div 2$

Which we had to prove. Does my proof hold or is it wrong? I don't want the whole answer, just a nod in the right direction. Any tips would be appriciated

Answer 1

This is what I have done so far.

$F(n+1)= 1 + F(n+1-2)$

$F(n+1) = (n+1)$ div $2$

$1 + (n+1)$ div $2 - 2= n$ div $2$

Which we had to prove.

The problem with this is that it's really not a proof. A proof consists of a sequence of sentences, each of which is true and includes (typically) some justification for its truth. The "statement/reason" format can help with this: on the left, you write statements, on the right, you write reasons. So converting what you've provided to that format gives something like what follows, where I've used "indenting" instead of left/right to provide statements and reasons.

1. $F(n+1)= 1 + F(n+1-2)$

   i. replacement of $n$ by $n+1$ in the third hypothesis.

2. $F(n+1) = (n+1)$ div $2$

   ii. [No justification given]

3. $1 + (n+1)$ div $2 - 2= n$ div $2$

   iii. This statement is actually false for $n = 2$, so ...

As you can see, when you start having to give reasons for each statement, proofs get a little trickier. Even the very first statement is incorrect, because in the third hypothesis, there's a restriction, which says that the formula works for $n > 1$. You have to include this in your statement, and then, having substituted $n+1$ for $n$, you have to modify the condition $n > 1$ to $n+1 > 1$, i.e., $n > 0$. So your proof would begin

1. $F(n+1)= 1 + F(n+1-2)$ for $n > 0$.

   i. replacement of $n$ by $n+1$ in the third hypothesis.

The second statement is what you're trying to prove, so it's no surprise that after a single statement, you cannot yet justify it.

In short: that first proof needs a lot of work.

Answer 2

Using the induction step you get that $F(n-1)=(n-1)$div$2$. Then use commun fraction properties to compute $F(n+1)$. As I see it, your proof doesn't make sence.