I can't find out what is wrong in this (computer science) induction exercise. Maybe I'm not cut out for this stuff.
Consider the following "proof" that the Fibonacci function, $F(n)$, defined as $F(1)=1$, $F(2)=2$, $F(n)=F(n-1)+F(n-2)$, is $O(n)$:
Base case ($n \leq 2)$: $F(1)=1$, which is $O(1)$, and $F(2)=2$, which is $O(2)$.
Induction step ($n > 2$): Assume that the claim is true for $n'<n$. Consider $n$. $F(n)=F(n-1)+F(n-2)$. By induction, $F(n-1)$ is $O(n-1)$ and $F(n-2)$ is $O(n-2)$. Then, $F(n)$ is $O((n-1)+(n-2))$ (by an identity presented earlier). Therefore $F(n)$ is $O(n)$, since $O((n-1)+(n-2))$ is $O(n)$.
Maybe it's the last part. $O((n-1)+(n-2))$ is $O(n)$. $O((n-1)+(n-2))$ does not equal $O(n)$ but of course $2n-3 \in O(n)$… and if we were to take $n=4$, we would have $O(3+2)=O(5)$, not $O(4)$…
I have some troubles with these "logic exercises"; I'm better at calculus… but perhaps I cracked it this time?
Best Answer
The error comes from the statement:
"Assume $F(n)=O(n)$ for $n < n'$."
This statement doesn't make sense. Saying $F(n)=O(n)$ is asymptotic notation, and defines behaviour of $F$ for all $n$ (larger than some $n''$). You cannot limit this behaviour to only a bounded set of $n$'ms beacuse that is not what big-$O$ means, and furthermore big-$O$ doesn't tell you anything about behaviour at a bounded space, but only about asymptotic behaviour.
A similar example would be "Assume $\lim_{n\to\infty}F(n) = c$ for $n\leq n'$."
In other words, as soon as you write $F(n)=O(n)$, you have defined the asymptotic behaviour of $F$. At that point your exercise would be finished, since $F(n)=O(n)$. The $n$ doesn't pay any role here, it's just notation. It would probably make things a lot clearer, if you instead wrote $F\in\{\text{Set of functions whose asymptotic behaviour at $\infty$ is linear}\}$. This is equivalent to $F(n)=O(n)$ or $F(n)\in O(n)$ (technically more correct).
Now it is more clear to see that $F\in\{\text{Set of functions whose asymptotic behaviour at $\infty$ is linear}\} \text{ for all } n\leq n'$ doesn't make sense.
Notice that $F(n)=O(n)+O(n-1)=O(n)$ is completely correct, and there is no errors here. Indeed, if $F(n)=O(n)$ and $F(n)=F(n)+F(n-1)$ then $F(n)=O(n)$, which is fine.
If, instead you had $F(n)=G(n)+G(n-1)$, and you had a hypothesis $G(n)=O(n)$, THEN you could prove that $F(n)=O(n)$. Try to do it, and understand the difference.
My suggestion is to try to re-write the exercise using only epsilon-delta notation. Then you will get stuck and understand what the underlying problem is.
Nevertheless this is a very nice problem that I hadn't encountered before! It can be useful in teaching big-$O$ notation.