En kluring om rationella tal

Tjena!

Här är en klurig uppgift från en gammal matematiktävling:

Visa att varje rationellt tal $\displaystyle \frac{p}{q}$ , där $\displaystyle 0 < \frac{p}{q} <1$ , kan skrivas på formen

$\displaystyle \frac{p}{q} = \sum_{j=1}^{n} \frac{1}{a_{j}},$

där $2 \leq a_{1} < a_{2} < \ldots < a_{n}$ är heltal.

Någon som känner sig manad? :)

Visa spoiler

Vi kan anta SGD(p,q)=1

Stark induktion över p:

Bas: Uppenbart sant för p=1, sätt bara a_1=q.

Antagande: Påståendet är sant för alla p <=P.

Induktionssteg: Betrakta 0<(P+1)/q<1. Det existerar ett minsta heltal k>=2 sådant att k(P+1)>q. För detta k gäller att k(P+1)-q<P+1. Vi får:

$\frac{P + 1}{q} - \frac{1}{k} = \frac{(P + 1) k - q}{k q}$

täljaren i HL är mindre än P+1 och kan enligt induktionsantagandet skrivas på önskad form.

Återstår endast att visa att 1/k inte förekommer i representationen av (P+1)/q-1/k. Men det följer av att

k är det minsta heltal sådant att k(P+1)>q att (k-1)(P+1)<q (likhet omöjligt pga relativt prima) av vilket följer (eftersom k >=2)

$\frac{P + 1}{q} < \frac{1}{k - 1} \leq \frac{2}{k}$

så

(P+1)/q-1/k<1/k

Svara