Fibonacci

[y6227]

Bonjour,

Voici ce que dit une correction :

A(0) = 1
A(1) = 1
A(n) = A(n-1) + A(n-2) + 1

On a donc A(n) = 2 Fib(n) - 1.

Bien que ce soit vrai, je n'arrive pas à comprendre comment peut-on deviner aussi simplement que A(n) était égal à 2 Fib(n) - 1.
Bien sur on sait que Fib (n) = Fib(n-1) + Fib(n-2) mais de là à passer aussi simplement à A(n) = 2 Fib(n) - 1, je ne vois vraiment pas comment le deviner.

Pouvez-vous m'éclairer ?

En vous remerciant par avance.

[nodjim]

Par observation puis vérification par récurrence, par exemple. C'est le plus rapide et le plus simple.