Here is another excellent solution from Andrei of Tudor Vianu
National College, Bucharest, Romania.
We are given
where
and
are solutions of the quadratic equation
and
.
(1) In the quadratic equation
with roots
amd
, using Viete's relations for the sum and product of the
roots, I obtain:
,
In the particular case of the equation
, I have:
,
(2)
as
satisfies
. Similarly for
.
(3) Here I shall prove that
,
and
and hence
is the
th Fibonacci number. First, I
calculate
and
:
and
(4) I shall prove by induction the statement
that
.
I know that
and by (3),
For
,
is
which is evidently true as 1 + 1
= 2.
For
,
is
which is evidently true as 1
+ 1 + 1 = 3.
For
,
is
which is evidently
true as 1 + 1 + 1 + 2 = 5.
Now I assume that
is true for a fixed
and I shall prove
that
is also true, that is:
and hence the
result is true for
. By the principle of mathematical
induction the statement
is true for all positive integer
values of
which completes the proof.