Where is the flaw in this proof by induction?

Question

I had a task to prove undermentioned property of the Fibonacci series. $$ a_2+a_4+a_6+...+a_{2n}=a_{2n+1}-1$$

where $a_1=1, a_2=1, a_3=2$.

For $n=3$:

$$a_2+a_4+a_6=1+3+8=12=a_7-1$$

Now let's assume that this is true for some $n$ and prove that this is true also for $n+1$.

$$a_2+a_4+a_6+...+a_{2n}+a_{2n+2}=a_{2n+3}-1$$ $$L=a_2+a_4+a_6+...+a_{2n}+a_{2n+2}=a_{2n+1}+a_{2n+2}-1=a_{2n+3}-1=R$$

It is proved! But then I quickly realised that $"-1"$ can be safely replaced by any number and the proof would still look valid. So what is going on? Are there any conditions that make induction invalid method?

Answer 1

That's what the basis step is for. Notice, you're proving a formula for all integers $n \ge 1$, and so the basis step is to check the formula for $n=1$. Once you've verified the basis step and the induction step then the formula is proved. But if you've verified only the induction step and not the basis step, then your proof is incomplete and, so far, invalid.

Here's what you might try to convince yourself. Start with some other recursive sequence that has the same inductive formula $a_n = a_{n-1} + a_{n-2}$ as the Fibonacci sequence, but has different starting values, say $a_1 = 2$ and $a_2 = 42$, so $a_3 = 44$, $a_4 = 86$, and so on. See if the induction step for proving your formula $a_2 + a_4 + ... + a_{2n} = a_{2n+1}-1$ is valid (it will be); see if the basis step is valid (it isn't); and most of all, see if the formula is true (it isn't).

Answer 2

It doesn't look like you did the inductive step, or the inductive hypothesis, right.

The inductive hypothesis is: $a_2+a_4+a_6+\dots+a_{2n}=a_{2n+1}-1$.

Then if we replace $n$ by $n+1$, we get: $a_2+\dots+a_{2(n+1)}=a_{2n+1}-1+a_{2n+2}=a_{2n+3}-1$, completing the proof. The last equality follows from the definition of the Fibonacci sequence.

$-1$ cannot be replaced by any other number, because then the base case won't be true.