Rekurentné postupnosti

Nech nejaký člen je štvorec $k^2$. Bude sa v aritmetickej postupnosti nachádzať aj štvorec $(k + c)^2$?

Nula je deliteľná každým číslom. Stačí nám teda nájsť také číslo $d$, že žiaden člen postupnosti nedáva po delení $d$ zvyšok $0$.

Vyhovuje $d = 3$. Dokonca sa zvyšky $1$ a $2$ pravidelne striedajú. Ostáva to len poriadne dokázať matematickou indukciou.

Rastúca aritmetická postupnosť $dn + c$ vlastne obsahuje od nejakej hodnoty všetky čísla, ktoré dávajú po delení $d$ zvyšok $c \mod d$. Nájdeme pre každé $d$ vo Fibonacciho postupnosti všetky zvyšky po delení $d$?

Nie, Fibonacciho čísla nikdy nedávajú zvyšok $4$ po delení $8$. Preto postupnosť $8n + 4$ neobsahuje žiadne Fibonacciho číslo.

Hrajte sa s úlohou. Skúšajte konkrétne jednoduché polynómy. Takto viete napr. prísť na to, že úloha platí pre konštantné a lineárne polynómy. Existuje ešte jedna pekná trieda polynómov (ľubovoľného stupňa), pre ktorú úloha ide ľahko ukázať.

Dokážte platnosť úlohy pre polynómy s nezápornými koeficientmi.

Pre polynóm $p(x)$ s nezápornými koeficientmi má $p(10^k)$ rovnaký ciferný súčet pre všetky čísla $k$ počnúc vhodnou hodnotou. Čo teraz so zápornými koeficientmi?

Problém zo zápornými číslami možno vyriešiť dosadením $10^k + c$ pre vhodné hodnoty $k$, $c$. Nasledujúce dve nápovede obsahujú postupne dva rôzne prístupy k tomu. Bez ujmy na všeobecnosti predpokladáme, že vedúci člen polynómu $p$ je kladný.

Prvý spôsob: Ukážte, že každý polynóm možno vyjadriť v tvare $a_n(x - c)^n + a_{n-1}(x-c)^{n-1} + \dots + a_2(x - c)^2 + a_1(x - c) + a_0$, kde $a_0, a_1, \dots, a_n$ sú nezáporné celé čísla.

Druhý spôsob: Dosaďte $x = 10^k + c$ a vyjadrite výrazy, ktoré sa objavia pri mocninách $10^k$. Ukážte, že vhodnou voľbou $c$ vieme docieliť, aby sme pri každej mocnine $10^k$ mali nezáporné číslo.

Ďalšie členy počítame pomocou funkcie $f(x) = x + k/x$. Pre potreby ďalšieho riešenia bude preto vhodné poznať vlastnosti tejto funckie. Najmä, kedy klesá, rastie a kde má extrémy. Ak s tým potrebujete pomoc, je v ďalšej nápovede.

$$f(x) = x + \frac{k}{x} = \left( \sqrt{x} - \sqrt{\frac{k}{x}} \right) + 2\sqrt{k} \ge 2\sqrt{k}.$$ Z toho vidíme, že funkcia $f$ nadobúda minimum pre $x = \sqrt{x}$ (vtedy pod druhou mocninou dostaneme $0$), na intervale $(0, \sqrt k\rangle$ je klesajúca a na intervale $\langle \sqrt k, \infty)$ zas rastúca.

Z využitím vlastností funkcie $f$ teraz môžete dokázať, že pre všetky celé $k \ge 2$ platí $k < a_k < k + 1.$

Ak teda sčítame $a_i + a_j$ pre $i, j \ge 2$, tak dostaneme desatinnú časť medzi $0$ a $1$, teda nie celé číslo.

Pre $a < 1$ sú v postupnosti všetky čísla, teda tvrdenie platí. Ostáva teda uvažovať $1 < a < 1 + 1/(b - 1)$. Nech sa mocnina $b^n$ nenachádza v postupnosti. Pozrite sa na prvý člen postupnosti menší ako $b^n$. Ako táto situácia bude vyzerať pri ďalších mocninách $b$-čka?

Nech $ka$ je najväčšie také číslo, ktoré je ešte menšie ako $b^n$. Keďže sa $b^n$ nevyskytuje v postupnosti, tak $(k+1)a \ge b^n + 1$. A teda $b^n - ka < a - 1$, teda $ka$ nesmie byť moc veľmi pod $b^n$. Pre ďalšie mocniny vieme ukázať, že $b^{n+i} - b^ika \le a - 1$.

Vzťah $b^{n+i} - b^ika = b^i(b^n - ka) \le a - 1$ je dobrý, lebo $b^i$ rastie exponenciálne, teda časom ľavá strana bude väčšia ako $a - 1$. Vtedy musí ďalší člen padnúť do intervalu $\langle b^{n+i}, b^{n+i} + 1)$.

Najskôr upravte rekurentný vzťah do krajšieho tvaru.

Použite substitúciu $b_n = a_n/a_{n-1}$. Dostanete tak postupnosť $b_n$ s krajším rekurentným vyjadrením. Potom $a_n = b_nb_{n-1}\dotsb_3b_2a_1$.

Pre postupnosť $b_n$ máme $b_2 = 2$, $b_3 = 12$ a $b_n = 6b_{n-1} - 8b_{n-2}$. Takúto postupnosť možno explicitne vyjadriť (pomocou štandardného postupu alebo aj tipnutím) ako $b_n = 4^{n-1} - 2^{n-1}$. Chceme tead ukázať, že $n$ delí nejaké $b_k$ pre $2 \le k \le n$.

Deliteľnosť vyplýva z Eulerovej vety, kde pre najväčšieho nepárneho deliteľa čísla $n$, označeného $d$, platí $4^{\varphi(d)} - 2^{\varphi(d)} \equiv 1 - 1 \equiv 0 \pmod n$. Deliteľnosť potrebnou mocninou dvojky je priama.

Rozpíšte si niekoľko prvých členov a rozmýšlajte, ako by sa na to dalo ísť. Viac uchopiteľne vyzerá nepriamy dôkaz (po ošetrení jednotky): ak $n$ je zložené číslo, tak $a_n$ je tiež zložené. Akého deliteľa by $a_n$ mohlo mať?

Dokážte, že ak $k \mid l$, tak $a_k \mid a_l$. Aké vlastnosti tejto postupnosti by to mohli zaručiť?

Všimnite si, že $a_n = 15a_{n-2} - 4a_{n-3} = a_3a_{n-2} - a_2a_{n-3}$. Nedal by sa takýto vzťah zovšeobecniť?

Pre túto postupnosť platí $a_n = a_{k+1}a_{n-k} - a_ka_{n-k-1}$.

Fixnite si $k$: to nám delí čísla $2k, 3k, 4k,\dots$. Ukazujte teda induktívne, že $a_k$ delí členy $a_{2k}, a_{3k}, a_{4k}, \dots$.

Existujú dva spôsoby, ako dokázať, že niečo nie je štvorec -- po delení vhodným číslom dáva nesprávny zvyšok alebo sa nachádza medzi dvomi štvorcami. Zvyšky nám tu moc nepomôžu (keďže $n = 3$ platí). Vypíšte si niekoľko prvých čísel postupnosti a skúmajte, medzi ktorými štvorcami sa $1 + 5a_na_{n+1}$ nachádza.

Chceme nájsť také $b_n$, že $b_n^2 < 1 + 5a_na_{n+1} < (b_n + 1)^2$ pre dostatočne veľké $n$. Vyskúšaním zistíme, že $b_3 = 250$ (ale tu z druhej nerovnosti máme rovnosť a ým pádom riešenie), $b_4 = 650$, $b_5 = 1700$, ... Čo za postupnosť je $b_n$? Ďalej existujú dve cesty: 1. Môžeme si všimnúť, že pre ňu platí rovnaký rekurentný predpis $b_{n+2} = 3b_{n+1} - b_n$. Teda vieme obe postupnosti vyjadriť explicitne a nerovnosti ukázať dosadením a overením. 2. Dá sa však všimnúť ešte niečo viac o $b_n$. Vyzerá v skutočnosti o niečo krajšie. Mimochodom, v oboch prípadoch nám stačí dokazovať, že $1 + 5a_na_{n+1} = b_n^2 + 501$ (teda pre $n > 3$) bude pod najbližším väčším štvorcom.

Všimnite si, že $b_n = a_n + a_{n+1}$. Chcete teda dokázať, že $1 + 5a_na_{n+1} = (a_n + a_{n+1})^2 + 501$.

Tento dôkaz ide indukciou. Treba sa kus pohrať s vyjadrovaním a upravovaním výrazov. Rozpíšte si $a_{n+1}$ cez rekurentný predpis, aby ste mohli využiť indukčný predpoklad.