Exercise1-12 <---> Exercise1-14

Exercise 1.13

Prove that $$ Fib(n) $$ is the closest integer to $$ \phi^n/\sqrt{5} $$, where $$ \phi = (1 + \sqrt{5})/2 $$.

Hint: Let $$ \psi = (1 - \sqrt{5})/2 $$. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that $$ Fib(n) = (\phi^n - \psi^n) / \sqrt{5} $$.

Ru: Докажите, что $$ Fib(n) $$ есть целое число, ближайшее к $$ \phi^n/\sqrt{5} $$, где $$ \phi = (1 + \sqrt{5})/2 $$.

Указание: пусть $$ \psi = (1 - \sqrt{5})/2 $$. С помощью определения чисел Фибоначчи (см. раздел 1.2.2) и индукции докажите, что $$ Fib(n) = (\phi^n - \psi^n) / \sqrt{5} $$.

Solution:

Step 1
Using induction lets prove that $$ Fib(n) = (\phi^n - \psi^n) / \sqrt{5} $$.

The basis.

For $$ n = 1,2 $$ the equality is satisfied:

$$ Fib(1) = (\phi^1 - \psi^1) / \sqrt{5} = 1 $$
$$ Fib(2) = (\phi^2 - \psi^2) / \sqrt{5} = 1 $$.

The inductive step.

Assuming that

$$ (\phi^k - \psi^k) / \sqrt{5} = Fib(k) $$ holds for all $$ k <= n $$, lets show that

$$ (\phi^{k+1} - \psi^{k+1}) / \sqrt{5} = Fib(k+1) $$.

Statement:

$$ \phi^{k+1} = \phi^k + \phi^{k-1} $$

$$ \psi^{k+1} = \psi^k + \psi^{k-1} $$

The proof of statement is trivial.

Now lets substitute the statement equalities into the hypothesis:

$$ (\phi^k + \phi^{k-1} - \psi^k + \psi^{k-1}) / \sqrt{5} = Fib(k+1) $$

$$ ((\phi^k - \psi^k) /\sqrt{5} + (\phi^{k-1} + \psi^{k-1} / \sqrt{5} = Fib(k+1) $$

Finally, using the inductive assumption, we have got:

$$ Fib(k) + Fib(k-1) = Fib(k+1) $$

which holds true.

Step 2
From the result, obtained in Step 1, it follows that

$$ |Fib(n) - \phi^n / \sqrt{5}| = |\psi^n / \sqrt{5}| $$.

$$ |\psi^n / \sqrt{5}| < 1/2 $$ for all $$ n >= 0 $$, therefore, $$ \phi^n / \sqrt{5} $$ is the closest integer to $$ Fib(n) $$

The end of proof.

Exercise1-12 <---> Exercise1-14

Comments

not quite trivial... theta squared = 1 + theta ... multiply it out to see. theta (n) = theta (n-2) * theta squared
  • = theta (n-2) * (1+theta) = theta (n-2) * theta(n-1)
Posted by CPE-124-182-142-84 at 2008-01-17 08:46:50 X

Since theta is one root of the equation x2 = x+1 so it is obvious that the statement holds in step 1,just by multiply both sides by x to the (n-1).

Posted by evans-wlan-180-181 at 2008-09-25 02:03:59 X

:) :)) :( ;) :\ |) X-( B) Markup

Exercise1-13 (last edited 2008-06-15 15:00:42 by chryana)