Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

The given starting points for this inductive proof are the following:

  1) the formulas, G(2x-2) = G(x)^2 - G(x-2)^2 and, G(2x-1) = G(x+1)G(x) - G(x-1)G(x-2)

or 2) the single formula for G(x) given above, in terms of the number a = ((5^.5) - 1)/2

So starting from 1), because 0 is the smallest natural, the base cases would be:

G(-2) = G(0)^2 - G(-2)^2 and G(-1) = G(1)G(0) - G(-1)G(-2)

But is this correct so far? I know my teacher defined natural numbers, in his class, to begin with x=0, but in this question he gave us, wouldn't it make more sense if the base cases started with x=1?

Also, G defines Fibonacci Numbers, and we are given the following:

G(0) = 0; G(1) = 1; for any x>=2, G(x) = G(x-1) + G(x-2)

share|cite|improve this question

You can choose your base case wherever you like. Here you are confusing the $x$ used in the recursion formula with the index of $G$. It only makes sense to start with $x=2$ for the first definition, in fact, because you don't have values $G(-1)$ and $G(-2)$. The second one would require $G(-1)$ for $x=1$ as well. Then the first one says $G(2)=G(2)^2-G(0)^2$. The second says $G(3)=G(3)G(2)-G(1)G(0)$. We will need starting values for $G(0),G(1)$ and maybe a selection of which possible value for $G(2)$ to use.

I don't understand what you mean by 2). You haven't said what closed form you think $G(n)$ obeys. Does it involve this $a$?

share|cite|improve this answer
Right, G defines Fibonacci numbers. @ross – user2898453 Oct 21 '13 at 0:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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