Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

My initial prompt is as follows:

For $F_{0}=1$, $F_{1}=1$, and for $n\geq 1$, $F_{n+1}=F_{n}+F_{n-1}$. Prove for all $n\in \mathbb{N}$:


Which, to my understanding, is Binet's Formula.

I came up with a proof strategy similar to that described here. But as you can see, it is considering the case of $F_n$, not $F_{n-1}$.

So, my question is: does the same strategy hold for $F_{n-1}$? If not, how is it different?

share|cite|improve this question

marked as duplicate by J. M., Amzoti, Alexander Gruber Jun 3 '13 at 3:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

@Whoever is voting to close: Why? This is a perfectly understandable question. – apnorton May 28 '13 at 22:54
up vote 5 down vote accepted

The problem that you’ve been given uses a less-standard indexing of the Fibonacci numbers. The usual definition has initial values $F_0=0$ and $F_1=1$; your $F_n$ is the usual $F_{n+1}$, and the usual $F_n$ is your $F_{n-1}$. Thus, where your link has $$\varphi^a=F(a)\varphi+F(a-1)\;,$$ you’ll need to write $$\varphi^a=F_{a-1}\varphi+F_{a-2}\;.$$ As a quick check, when $a=2$ that gives you $\varphi^2=F_1\varphi+F_0=\varphi+1$, which you can see from the link is correct.

(I’m assuming here that your proof really does follow pretty much the pattern in the link. You can also just do a straight induction: the induction step is the same whichever indexing you use.)

share|cite|improve this answer

It's impossible to tell without reading your proof, but induction (as a principle) will work regardless of whether you consider $n$ or $n-1$. The only difference is the indexing of the base case, but with the shift $n \mapsto n-1$ you needn't worry about introducing a "gap" at all.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.