Hogyan lehet bebizonyítani, hogy minden pozitív racionális szám előáll véges sok különböző 1/k alakú tört összegeként?

Itt megtalálod Fibonacci algoritmusát: [link]

Lásd be, hogy az algoritmusa mindig véges sok lépésben véget ér.

De kiindulhatsz a szakaszosan végtelen kettedestörtekből is (a tizedestört kettes számrendszerbeli megfelelője).

1. Lépés: addig választod az 1/1, 1/2, 1/3 számokat, amíg tudod. Ami "kimarad", mert pl. az 1/n-et már nem tudod választani, az kisebb lesz, mint 1/n. Tehát nem kell aggódnod amiatt, hogy az eddig választott számokkal ütközni fog. Ugyanakkor mostantól 1-nél kisebb számod van.

2. Van egy 1-nél kisebb szakaszosan végtelen kettedestörted, pl. 0.101(10110) (így jelölöm az ismétlődő szakaszt).

Ha 5 hosszú a szakasz, akkor vegyük észre, hogy 1/(2^5-1) = 1/31 = 0.(00001).

Tehát az ötödik számjegytől egyszerűen 1/31-gyel és eltoltjaival lefedheted az ismétlődő szakaszt. A példában van egy "piszkos" rész, majd egy 5-hosszú szakasz, ami felírható 3 darab (00001) szakasz összegeként. Ha a szakasz túl elöl kezdődik, akkor egyszerűen hátrébb veszed fel. A piszkos rész felírása pedig egyszerűen kettőhatványokkal megy.

0.101(10110) = 0.10110(11010) = 0.10110 + 0.0(00001) + 0.00(00001) + 0.0000(00001) = (1/2 + 1/8 + 1/16) + 1/(31*2) + 1/(31*4) + 1/(31*16).

Megjegyzés:

Ez a megoldás csak (2^n-1)*2^k alakú törteket használ 1-nél kisebb számok esetén.