Vrftsjtryk

I am currently studying induction. I understand the how the principle is supposed to work, I can follow and understand a proof by induction quite fine (the ones I've seen anyway), but actually using it to prove a statement is a bit more difficult. I have this excercise:

Let $a$ and $b$ be roots of the equation $x^2-x-1=0$. Prove that for every $n in N$ the number $a^n+b^n$ is an integer.

I need some help from the beginning: How do I set up the proof? Does knowing that $a$ and $b$ are roots of $x^2-x-1=0$ help me in any way? If so how? How do I know if a and b are integers? Of course the sum of the integer powers of two integers would still be an integer, but I'm not told what they are, and roots of a quadratic equation can also be not integers.

How would I prove a basis step? Should I solve the equation twice, once assuming $a=1$ and once $b=1$, and then sum the result?

There is a somewhat thorough confusion you seem to be going through. Let me ease your malaise.

See, in order to "prove by induction" a statement concerning a property of something indexed by the natural numbers :

• Formulate the statement you want to prove : that is, to each natural number, associate a statement you want to prove.




• Prove the statement corresponding to the natural number $1$.




• Prove the statement corresponding to the natural number $n$, assuming that the statements corresponding to $n-1$ is true.

It is that simple. Or is it?

Step one : the statement is sometimes given to us. Thus, we may associate to the natural number $n$, the statement : "$a^n+b^n$ is an integer, where $a,b$ are the roots of the equation $x^2-x-1 = 0$".

Remarks :

• $a,b$ are fixed, and given to be the roots of a quadratic equation.




• As pointed out, $a,b$ need not be integers (and are not in this case!), but then, $0.5 + 1.5 = 2$ is an integer even though $0.5$ and $1.5$ are not. So, for the sum of two numbers to be an integer they themselves don't need to be integers.

Unfortunately, the above "assignment of statements" doesn't quite work out : a teeny weeny little issue crops up at the end. I'll have to explain why.

Step two : Prove the statement corresponding to $n = 1$.

This is : $a+b$ is an integer.

Ok, so here we need to pull out our knowledge about equations. Since the roots of $x^2-x-1$ are $a,b$, the unique quadratic polynomial with roots $a,b$ is $(x-a)(x-b)$. Thus, $(x-a)(x-b) = x^2-x-1$.

Expanding, $x^2 - (a+b)x + ab = x^2-x-1$. Since two polynomials are equal if and only if all their coefficients : equating the coefficients of $x$ gives us $a+b = 1$, which is an integer.

Thus, the statement corresponding to $n=1$ is proved.

We note a little more : comparing the constants, $ab = -1$.

Step two : For the general case, we need to use somehow that $a^{k} + b^{k}$ is an integer(for $k < n$), to show that $a^n+b^n$ is an integer.

Now, let us recall what you mentioned : the product of two integers is an integer, the sum of two integers is an integer. Suppose I could obtain $a^n + b^n$ as a sum / product or such a combination of smaller $a^k+b^k$, then I would be done by the observation in the previous paragraph.

A little bit of playing around gives the brilliant :
$$
a^n+b^n = (a+b)(a^{n+1} + b^{n+1}) - ab(a^{n-2} + b^{n-2})
$$

since we know that $ab = -1$, this gives that $a^n+b^n = (a^{n-1}+b^{n-1}) + (a^{n-2}+b^{n-2})$. The sum of two integers is an integer , job done, induction complete.

So, for proving the statement pertaining to $n$, we needed the statements pertaining to $n-1$ and $n-2$. Sometimes, more statements may be required, sometimes less.

Ok, so where was the issue above?

The issue is this : for $n=2$, the induction is not true. Because, we have secretly used the fact that $a^0+b^0 = 2$ is an integer while using the identity in the magic step, if we put $n = 2$ in it. This was not part of the induction at all : it is an independent observation. So, one must be careful while performing the inductive step : using more "previous steps" in induction will require more observations like the above from us, however trivial they may be.

Essentially, $n=2$ should be included in the "base case" as an independent observation.

ASIDE : Let $x_k = a^k+b^k$ be the sequence we were asked to show as integers above. The analysis above shows that $x_1 = 1$,$x_2 = 3$ , and $x_{k+2} = x_{k+1} + x_k$. Can you identify some sort of Fibonacci-type sequence here? Read up on Lucas sequences here : and check if they have something to do with sums of nth powers of the roots of some quadratic equation.

EDIT : The relation causing much angst is
$$
a^n+b^n =(a+b)(a^{n-1}+b^{n-1}) - ab(a^{n+2}+b^{n-2})
$$

See, always remember the golden rule : two polynomials (in many variables) are equal if and only if the coefficients of every monomial present in either side are equal.

This golden rule we plan to use.

Now, remember what I said earlier : we want to write $a^n+b^n$ as a sum/product or a combination of terms consisting of $a^k + b^k$ with $k<n$, so that we can proclaim that the sum/product of integers is an integer.

Thus, we should start with , say how to "reach" $a^n+b^n$ from $a^{n-1}+b^{n-1}$. This is the term out of those we know as being integral, which seems closest to $a^n+b^n$.

We are at step :
$$
a^n+b^n = ????(a^{n-1}+b^{n-1})????
$$

Where I have indicated that the right hand side is unknown, but involves $a^{n-1} + b^{n-1}$.

How do we reach? Use the golden rule : since we have an $a^n$ on the LHS(left hand side), we need one on the RHS(right hand side). How do we get this? Simple : multiply $a^{n-1}$ by $a$ to get $a^n$. Ok.

But then, the $b^{n-1}$ also gets multiplied by $a$. So we also land up with an extra $b^{n-1}a$ on the right hand side, if we multiply by $a$.

We are now at:
$$
a^{n}+b^n = a(a^{n-1} + b^{n-1}) + ???? = a^n + ab^{n-1} + ???
$$

Do the same thing with $b^n$ : we need $b^n$ on the right hand side, so multiply $b^{n-1}$ with $b$ to get $b^n$. However, since $a^{n-1} + b^{n-1}$ needs to come together while multiplying, we need to keep in mind that $b a^{n-1}$ will also appear.

Now we are at:
$$
a^{n} + b^n = a(a^{n-1} + b^{n-1}) + b(a^{n-1}+b^{n-1}) + ?????
$$

Now, we look, and realize that every term on the left has the correct degree. Therefore, ???? should consist of terms being cancelled out, so that all other coefficients, such as $ab^{n-1}$ and $ba^{n-1}$, are zero, because these terms don't appear on the left hand side.

In essence, we have:
$$
a^n+b^n = a(a^{n-1} + b^{n-1}) + b(a^{n-1} + b^{n-1}) - ba^{n-1} - ab^{n-1}
$$

Now, thankfully, things fall into position. Thankfully, one gleefully collects terms , and realizes that $ba^{n-1} + ab^{n-1} = ab(a^{n-2} + b^{n-2})$. Putting things together :
$$
a^n+b^n = (a+b)(a^{n-1} + b^{n-1}) - ab(b^{n-2} + a^{n-2})
$$

Note how thankful I am. If things did not work out via the golden rule, then I would have to use some other way to figure things out.

In general, polynomial identities like this are the stuff of gods. Granted that one can use the "golden rule" to some effect, but identities like this:
$$
(a^2+b^2)(c^2+d^2) = (ac+bd)^2 + (ad-bc)^2
$$

involve "completing the square", another technique which is popular. You will see more of these identities as you go along, but the subject is so varied that you will see a different way of deriving each one.

I'll try to point you in the right direction here.

For the base case, we need to show $a+b$ is an integer. Use the factorization $x^2-x-1=(x-a)(x-b)$

To use induction, we need some way of reducing the problem to a problem of lower degree. Here the relations $a^2=a+1$ and $b^2=b+1$ look promising, because they reduce the exponent involved from $2$ to $1$, so hopefully they can be used to reduce the exponent from $n$ to $n-1$

The trick is to construct $a^n+b^n$ from sums of a lower degree.

Then notice that

$$(a+b)(a^{n-1}+b^{n-1})=a^n+b^n+ab(a^{n-2}+b^{n-2}).$$

But from the Vieta's formulas,

$$a+b=1$$ and $ab=-1$ so that the following recurrence holds:

$$a^n+b^n=a^{n-1}+b^{n-1}+a^{n-2}+b^{n-2}.$$