Paradox - What is wrong with this proof that proves a false assertion? Theorem: Let $a_{n}=a_{n-1}+1, a_1=1$. For any $n$, in order to compute $a_n$, it is necessary to compute $a_i$ for each $i=1,\dots,n-1$, which takes $\Theta(n)$ time.
Proof: This is vacuously true for $n=1$. Assume true for $n=k-1$. Prove true for $n=k$. In order to compute $a_{k-1}+1$, it is necessary to compute $a_{k-1}$. Then since $a_k=a_{k-1}+1$, in order to compute $a_k$, it is necessary to compute $a_{k-1}$. By the induction hypothesis, in order to compute $a_{k-1}$, it is necessary to compute $a_i$ for each $i=1,\dots,k-2$. Hence, in order to compute $a_k$, it is necessary to compute $a_i$ for each $i=1\dots,k-1$. QED
What is wrong with this proof? It seems valid to me, even though the theorem is false.
 A: In your induction step, you made the additional assumption (beyond the inductive hypothesis) that it was necessary to compute $a_{k-1}$ in order to compute $a_k$. That's hardly the case, as simple inspection of the recursive definition gives us the closed-form definition $a_n:=n$ for all $n$.
A: The fallacy is at a simpler level than anything about algorithms or runtime complexity.   The point is that 

a sequence that satisfies one definition can also satisfy many other definitions. 

The alternative definitions might include ones that do not use recursion, or are more computationally efficient when converted to an algorithm.  Therefore,

having one definition of a sequence does not indicate its complexity (in any sense of that word), only an upper bound to the complexity.

As an example, the sequence defined recursively by $$a_n = a_{n-1} + a_{n-2} - a_{n-3}$$ for $n>3$ and $a_1=a_2=a_3=1$, is constant.  It takes an exponential number of operations to compute $a_n$ from that recursive definition, but the sequence also be computed from a different definition, $(\forall n )a_n = 1$.
Proving that different definitions specify the same sequence can be more logically complicated than applying either definition alone.  Fermat's Last Theorem can be seen as an alternative definition of the sequence $0,0,0,.\dots$ but the demonstration involved a few thousand pages of theory.
