WisFaq!

Bewijs m.b.v volledige inductie

Ik kom niet helemaal uit de inductiestap bij de volgende vraag: Bewijs met volledige inductie dat voor elke gehele n>0 de grootste gemeenschappelijke deler van de Fibonacci-getallen Bn en Bn+1 gelijk aan 1 is.

M. Smids
28-4-2002

Antwoord

Voor n = 1 klopt het overduidelijk, want B₁ = 1 en B₂ = 1, en de GGD van het duo 1 en 1 is natuurlijk 1.

Stel nu dat je bewering waar is voor n = k. De GGD van B_k en B_k+1 is dus gelijk aan 1.

Stel d = GGD(B_k+1,B_k+2)

Dan is d deelbaar op beide getallen en dus ook op hun verschil!
Maar dat verschil is natuurlijk gelijk aan B_k, want op die manier is de rij van Fibonacci gevormd.
Maar dan is d dus deelbaar op B_k , en d is óók deelbaar op B_k+1.
Dus is d een gemeenschappelijke deler van deze twee termen, en omdat hun grootste gemene deler 1 is, is d zelf gelijk aan 1.

MBL
28-4-2002