Wanneer belandt de rij op een kwadraat?

Een rij groeit telkens met het gehele deel van de vierkantswortel van haar laatste term. Door eerst veel termen uit te rekenen, wordt zichtbaar waarom sommige kwadraten wel worden geraakt en andere net worden overgeslagen. Daarna bewijzen we het patroon stap voor stap.

Infobox

Onderwerpen: Rijen, getaltheorie
Probleemoplossingstechnieken: Beginwaarden berekenen, regelmaat zoeken, werken met intervallen, hulpvariabele invoeren, inductie
Moeilijkheid: Moeilijk
Competitie: Indian National Mathematical Olympiad, finale
Jaar: 2026
Opgavenummer: 1

Opgave

Laat $x_1,x_2,x_3,\ldots$ een rij van positieve gehele getallen zijn, als volgt gedefinieerd: $x_1=1$ en voor elke $n\geq 1$ geldt

$x_{n+1}=x_n+\lfloor\sqrt{x_n}\rfloor.$

Bepaal alle positieve gehele getallen $m$ waarvoor $x_n=m^2$ voor een zekere $n\geq 1$ . Hierbij stelt $\lfloor x\rfloor$ voor elk reëel getal $x$ het grootste gehele getal voor dat kleiner dan of gelijk aan $x$ is.

Eerste idee

Tussen $k^2$ en $(k+1)^2$ neemt de rij telkens met $k$ toe. Om precies op $k^2$ te belanden, moet daarom eerst de term $k^2-(k-1)$ voorkomen. De beginwaarden tonen dat dit bij $k=1,2,4,8,16,\ldots$ lukt. We meten vervolgens bij elk kwadraat hoeveel de rij dat kwadraat heeft overschreden.

Observatieronde

De eerste termen

We berekenen eerst een stuk van de rij. De kwadraten zijn rood weergegeven:

$1$ , $2$ , $3$ , $4$ , $6$ , $8$ , $10$ , $13$ , $16$ , $20$ , $24$ , $28$ , $33$ , $38$ , $44$ , $50$ , $57$ , $64$ , $72$ , $80$ , $88$ , $97$ , $106$ , $116$ , $126$ , $137$ , $148$ , $160$ , $172$ , $185$ , $198$ , $212$ , $226$ , $241$ , $256$ , $272$ , $288$ , $304$ , $321$ , $338$ , $356$ , $374$ , $393$ , $412$ , $432$ , $452$ , $473$ , $494$ , $516$ , $538$ , $561$ , $584$ , $608$ , $632$ , $657$ , $682$ , $708$ , $734$ , $761$ , $788$ , $816$ , $844$ , $873$ , $902$ , $932$ , $962$ , $993$ , $1024$ , $\ldots$

De eerste kwadraten in de rij zijn

$1=1^2,\qquad4=2^2,\qquad16=4^2,\qquad64=8^2,\qquad256=16^2,\qquad1024=32^2.$

Eerste vaststellingen

Tussen twee opeenvolgende kwadraten is de stapgrootte constant. Als $k^2\leq x_n<(k+1)^2$ , neemt de rij telkens met $k$ toe. Tussen $16$ en $25$ zien we $16,20,24,28$ . Tussen $25$ en $36$ zien we $28,33,38$ .
Om op $k^2$ te belanden, moet de juiste term vlak ervoor voorkomen. Die term is $k^2-(k-1)$ . Voor $16$ is dat $13$ , en die term komt voor. Voor $25$ zou $21$ moeten voorkomen, maar de rij gaat van $20$ naar $24$ en dan naar $28$ . Voor $36$ zou $31$ nodig zijn, maar de rij gaat van $28$ naar $33$ en dan naar $38$ .
Bij machten van $2$ lukt dit, bij de andere waarden niet. Voor $k=4$ staat $13=16-3$ in de rij en voor $k=8$ staat $57=64-7$ in de rij. Voor $k=5,6,7$ ontbreken respectievelijk $21,31,43$ , zodat $25,36,49$ niet voorkomen.

Nu bewijzen we deze waarnemingen.

Uitwerking

Stap 1: de rij bereikt elk interval tussen twee kwadraten

De rij is strikt stijgend, want elke stap is minstens $1$ . Ze is daardoor ook onbegrensd.

Neem $k\geq2$ en kijk naar de eerste rijterm die minstens $k^2$ is. De term vlak ervoor is kleiner dan $k^2$ , zodat de stap vanuit die term hoogstens $k-1$ bedraagt. De eerste term die minstens $k^2$ is, is dus hoogstens

$(k^2-1)+(k-1)=k^2+k-2<(k+1)^2.$

Er ligt bijgevolg minstens één rijterm in elk interval $[k^2,(k+1)^2)$ .

Stap 2: binnen zo’n interval zijn alle stappen gelijk

Als $k^2\leq x_n<(k+1)^2$ , dan is $k\leq\sqrt{x_n}<k+1$ . Dus $\lfloor\sqrt{x_n}\rfloor=k$ , en $x_{n+1}=x_n+k$ .

Stap 3: wanneer wordt een kwadraat bereikt?

De term vlak vóór $k^2$ ligt volgens stap 1 in $[(k-1)^2,k^2)$ . Volgens stap 2 is de volgende stap dan $k-1$ . Daarom kan $k^2$ alleen worden bereikt vanuit $k^2-(k-1)$ . Omgekeerd: als deze term voorkomt, is de volgende term inderdaad $k^2$ .

Stap 4: de eerste term na elk kwadraat volgen

Schrijf de eerste rijterm in $[k^2,(k+1)^2)$ als $k^2+a_k$ . De waarde $a_k$ meet hoeveel de rij $k^2$ heeft overschreden. We hebben $a_1=0$ , en voor $k\geq2$

$0\leq a_k\leq k-2.$

Er zijn twee gevallen.

Geval 1: $a_k=0$ . Vanuit $k^2$ zijn drie stappen van grootte $k$ nodig om voor het eerst minstens $(k+1)^2=k^2+2k+1$ te bereiken:

$k^2,\quad k^2+k,\quad k^2+2k,\quad k^2+3k.$

Omdat $k^2+3k=(k+1)^2+(k-1)$ , geldt $a_{k+1}=k-1$ . Zo krijgen we vanuit $16$ de termen $20,24,28$ , en dus $a_5=3$ .

Geval 2: $a_k>0$ . Omdat $1\leq a_k\leq k-2$ , is één stap niet genoeg om $(k+1)^2$ te bereiken, maar zijn twee stappen wel genoeg. De eerste term in het volgende interval is

$k^2+a_k+2k=(k+1)^2+(a_k-1).$

Daarom geldt $a_{k+1}=a_k-1$ . In het voorbeeld:

$a_5=3,\qquad a_6=2,\qquad a_7=1,\qquad a_8=0.$

Dit correspondeert met $28=25+3$ , $38=36+2$ , $50=49+1$ en $64=64+0$ . Samengevat:

$a_{k+1}=\begin{cases} k-1,&\text{als }a_k=0,\\ a_k-1,&\text{als }a_k>0. \end{cases}$

Stap 5: de nulwaarden zijn precies de machten van twee

We bewijzen met inductie dat $a_{2^r}=0$ voor elk geheel getal $r\geq0$ , en dat tussen $2^r$ en $2^{r+1}$ geen andere nulwaarde ligt.

We beginnen met $a_1=0$ . Stel dat $a_{2^r}=0$ . Dan is $a_{2^r+1}=2^r-1$ . Daarna daalt de waarde bij elke volgende stap met $1$ , zolang ze positief is. Voor $2^r+1\leq k\leq2^{r+1}$ geldt dus

$a_k=2^{r+1}-k.$

Deze waarde is positief als $2^r<k<2^{r+1}$ , en wordt voor het eerst opnieuw $0$ als $k=2^{r+1}$ . Daarmee is de inductie voltooid.

De rij bevat $k^2$ precies wanneer $a_k=0$ . Dat gebeurt exact voor machten van $2$ . Alle gezochte positieve gehele getallen zijn daarom

$\boxed{m=2^r\quad(r=0,1,2,\ldots)}.$

Probleemoplossingstechnieken

Beginwaarden berekenen: De eerste termen maken zichtbaar welke kwadraten voorkomen.
Regelmaat zoeken: De stapgrootte blijft tussen opeenvolgende kwadraten constant.
Werken met intervallen: De rij wordt verdeeld in stukken met een vaste stapgrootte.
Hulpvariabele invoeren: De overschrijding $a_k$ meet de afstand tot het vorige kwadraat.
Inductie: De nulwaarden zijn precies $1,2,4,8,\ldots$ .

Wiskunde is leuk