telprobleem

Eerst maken we ter illustratie een tabel voor het aantal mogelijkheden voor kleinere getallen die voldoen aan de gegeven eisen.

De bovenkant duidt op het aantal cijfers van het getal, benoem dit aantal met $n$.
De linkerkant is het laatste cijfer waarop de mogelijkheden eindigen, noem dit $k$
Samen geeft het aantal mogelijkheden eindigend op een bepaald cijfer $k$ van een bepaalde lengte $n$, noem dit $(n,k)$. We nemen ook nog een totaal van aantal mogelijkheden per kolom, noem dit $S_n$ (uiteraard gelijk aan $S_n=(n,1)+(n,3)+(n,5)+(n,7)+(n,9)$). Gevraagd is dus $S_{1000}$.

We hebben de tabel gevormd door eerst voor 1 cijfer overal 1 mogelijkheid te noteren. Daarna moet gelden $(n,k)=(n-1,k-2)+(n-1,k+2)$ voor $k=3,5,7$ en $(n,1)=(n-1,3)$ en $(n,9)=(n-1,7)$. Voorgaande formules zijn gewoon vertalingen van de gegeven eisen: men kan enkel achter een mogelijkheid met $n-1$ cijfers eindigend op $k-2$ of $k+2$ het cijfer $k$ plaatsen. Behalve wanneer $k=1$ of $k=9$ kan maar 1 cijfer achter de vorige mogelijkheden worden geplaatst, nl. $3$ of $7$. In het bewijs zullen bovenstaande identiteiten gebruikt worden.

Enkele vermoedens stijgen uit de tabel op, vanaf $n=4$ lijkt het erop dat er enkel nog 3-vouden voorkomen in de tabel. Zelfs nog specifieker, het lijkt dat het vanaf $n=2$ klopt dat $S_{n+2}=3S_n$. Dit gaan we bewijzen, maar daarvoor hebben we eerst een ander lemmaatje nodig:

lemma 1: $(n,1)+(n,9)=(n,5)$ voor $n\geq 2$

$(n,1)=(n-1,3)$
$(n,9)=(n-1,7)$
Tel nu deze gelijkheden op:
$(n,1)+(n,9)=(n-1,3)+(n-1,7)=(n,5)$

lemma 2: $S_{n+2}=3S_n$ voor $n\geq 2$

$S_{n+2}=(n+2,1)+(n+2,3)+(n+2,5)+(n+2,7)+(n+2,9)$
$=(n+1,3)+(n+1,1)+(n+1,5)+(n+1,3)+(n+1,7)+(n+1,5)+(n+1,9)+(n+1,7)$
$=(n,1)+(n,5)+(n,3)+(n,3)+(n,7)+(n,1)+(n,5)+(n,5)+(n,9)+(n,3)+(n,7)+(n,7)+(n,5)+(n,9)$
$=2(n,1)+3(n,3)+4(n,5)+3(n,7)+2(n,9)$
$=3(n,1)+3(n,3)+3(n,5)+3(n,7)+3(n,9)$ (lemma 1)
$=3S_n$

Nu resteert ons nog het antwoord te zoeken met de gevonden recursie:
$S_{1000}=3S_{998}=3^2S_{996}=3^3S_{994}=\dots =3^{499}S_2$
$=$$8*3^{499}$ $\blacksquare$