Rekurentné postupnosti
Autor: Jozef Rajník
Letná škola matematiky, 18. 7. 2022
PDF s celou prednáškou
Úloha 1
Majme nekonečnú aritmetickú postupnosť, ktorá obsahuje iba prirodzené čísla. Dokážte, že ak obsahuje nejakú druhú mocninu prirodzeného čísla, potom obsahuje nekonečne veľa druhých mocnín prirodzených čísel.
KMS 07/08-Z3-7
Nápoveda 1
Nech nejaký člen je štvorec MATH_STASH_0_ENDSTASH. Bude sa v aritmetickej postupnosti nachádzať aj štvorec MATH_STASH_1_ENDSTASH?
Úloha 2
Majme postupnosť $a_1, a_2, a_3, \dots$ definovanú takto:
-
$a_1 = 1$, $a_2 = 2$,
-
ak $a_n \cdot a_{n+1}$ je párne, tak $a_{n+2} = 5a_{n+1} - 3a_n$,
-
ak $a_n \cdot a_{n+1}$ je nepárne, tak $a_{n+2} = a_{n+1} - a_n$.
Ukážte, že $a_n$ nemôže byť nula pre žiadne prirodzené číslo $n \ge 3$.
KMS 02/03-L3-8
Nápoveda 1
Nula je deliteľná každým číslom. Stačí nám teda nájsť také číslo MATH_STASH_11_ENDSTASH, že žiaden člen postupnosti nedáva po delení MATH_STASH_12_ENDSTASH zvyšok MATH_STASH_13_ENDSTASH.
Nápoveda 2
Vyhovuje MATH_STASH_14_ENDSTASH. Dokonca sa zvyšky MATH_STASH_15_ENDSTASH a MATH_STASH_16_ENDSTASH pravidelne striedajú. Ostáva to len poriadne dokázať matematickou indukciou.
Úloha 3
Nech $F_1 = F_2 = 1$ a $F_{n+2} = F_{n+1} + F_n$ pre $n \in \mathbb{N}$ (známa Fibonacciho postupnosť). Zistite, či existuje nekonečná rastúca aritmetická postupnosť prirodzených čísel, ktorá neobsahuje žiadne číslo z Fibonacciho postupnosti.
KMS 05/06-L1-9
Nápoveda 1
Rastúca aritmetická postupnosť MATH_STASH_20_ENDSTASH vlastne obsahuje od nejakej hodnoty všetky čísla, ktoré dávajú po delení MATH_STASH_21_ENDSTASH zvyšok MATH_STASH_22_ENDSTASH. Nájdeme pre každé MATH_STASH_23_ENDSTASH vo Fibonacciho postupnosti všetky zvyšky po delení MATH_STASH_24_ENDSTASH?
Nápoveda 2
Nie, Fibonacciho čísla nikdy nedávajú zvyšok MATH_STASH_25_ENDSTASH po delení MATH_STASH_26_ENDSTASH. Preto postupnosť MATH_STASH_27_ENDSTASH neobsahuje žiadne Fibonacciho číslo.
Úloha 4
Nech $p(x)$ je polynóm s celočíselnými koeficientmi a nech $c_n$ je ciferný súčet čísla $p(n)$. Dokážte, že v nekonečnej postupnosti $c_1,c_2,c_3,\dots$ sa nejaká hodnota vyskytne nekonečne veľakrát.
KMS 08/09-Z1-11
Nápoveda 1
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ť.
Nápoveda 2
Dokážte platnosť úlohy pre polynómy s nezápornými koeficientmi.
Nápoveda 3
Pre polynóm MATH_STASH_32_ENDSTASH s nezápornými koeficientmi má MATH_STASH_33_ENDSTASH rovnaký ciferný súčet pre všetky čísla MATH_STASH_34_ENDSTASH počnúc vhodnou hodnotou. Čo teraz so zápornými koeficientmi?
Nápoveda 4
Problém zo zápornými číslami možno vyriešiť dosadením MATH_STASH_35_ENDSTASH pre vhodné hodnoty MATH_STASH_36_ENDSTASH, MATH_STASH_37_ENDSTASH. 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 MATH_STASH_38_ENDSTASH je kladný.
Nápoveda 5
Prvý spôsob: Ukážte, že každý polynóm možno vyjadriť v tvare MATH_STASH_39_ENDSTASH, kde MATH_STASH_40_ENDSTASH sú nezáporné celé čísla.
Nápoveda 6
Druhý spôsob: Dosaďte MATH_STASH_41_ENDSTASH a vyjadrite výrazy, ktoré sa objavia pri mocninách MATH_STASH_42_ENDSTASH. Ukážte, že vhodnou voľbou MATH_STASH_43_ENDSTASH vieme docieliť, aby sme pri každej mocnine MATH_STASH_44_ENDSTASH mali nezáporné číslo.
Úloha 5
Postupnosť reálnych čísel $a_1, a_2, a_3, \dots$ spĺňa $1 < a_1 < 2$ a pre všetky prirodzené $k$ platí $$a_{k+1} = a_k + \frac{k}{a_k}.$$ Dokážte, že existuje najviac jedna dvojice $(i,j)$, že $i < j$ a zároveň $a_i + a_j$ je celé číslo.
KMS 10/11-2Z-13
Nápoveda 1
Ďalšie členy počítame pomocou funkcie MATH_STASH_52_ENDSTASH. 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.
Nápoveda 2
MATH_STASH_53_ENDSTASH Z toho vidíme, že funkcia MATH_STASH_54_ENDSTASH nadobúda minimum pre MATH_STASH_55_ENDSTASH (vtedy pod druhou mocninou dostaneme MATH_STASH_56_ENDSTASH), na intervale MATH_STASH_57_ENDSTASH je klesajúca a na intervale MATH_STASH_58_ENDSTASH zas rastúca.
Nápoveda 3
Z využitím vlastností funkcie MATH_STASH_59_ENDSTASH teraz môžete dokázať, že pre všetky celé MATH_STASH_60_ENDSTASH platí MATH_STASH_61_ENDSTASH
Nápoveda 4
Ak teda sčítame MATH_STASH_62_ENDSTASH pre MATH_STASH_63_ENDSTASH, tak dostaneme desatinnú časť medzi MATH_STASH_64_ENDSTASH a MATH_STASH_65_ENDSTASH, teda nie celé číslo.
Úloha 6
Prirodzené číslo $b$ je väčšie ako jedna. Pre kladné reálne číslo $a$ platí $1/a + 1/b > 1$. Dokážte, že potom postupnosť čísel $\lfloor a \rfloor, \lfloor 2a \rfloor,\lfloor 3a \rfloor,\dots$ obasahuje nekonečne veľa zložených celočíselných mocnín čísla $b$.
KMS 09/10-L3-11
Nápoveda 1
Pre MATH_STASH_71_ENDSTASH sú v postupnosti všetky čísla, teda tvrdenie platí. Ostáva teda uvažovať MATH_STASH_72_ENDSTASH. Nech sa mocnina MATH_STASH_73_ENDSTASH nenachádza v postupnosti. Pozrite sa na prvý člen postupnosti menší ako MATH_STASH_74_ENDSTASH. Ako táto situácia bude vyzerať pri ďalších mocninách MATH_STASH_75_ENDSTASH-čka?
Nápoveda 2
Nech MATH_STASH_76_ENDSTASH je najväčšie také číslo, ktoré je ešte menšie ako MATH_STASH_77_ENDSTASH. Keďže sa MATH_STASH_78_ENDSTASH nevyskytuje v postupnosti, tak MATH_STASH_79_ENDSTASH. A teda MATH_STASH_80_ENDSTASH, teda MATH_STASH_81_ENDSTASH nesmie byť moc veľmi pod MATH_STASH_82_ENDSTASH. Pre ďalšie mocniny vieme ukázať, že MATH_STASH_83_ENDSTASH.
Nápoveda 3
Vzťah MATH_STASH_84_ENDSTASH je dobrý, lebo MATH_STASH_85_ENDSTASH rastie exponenciálne, teda časom ľavá strana bude väčšia ako MATH_STASH_86_ENDSTASH. Vtedy musí ďalší člen padnúť do intervalu MATH_STASH_87_ENDSTASH.
Úloha 7
Nech $a_1 = 1$, $a_2 = 2$, $a_3 = 24$ a $$\begin{aligned} %a_1 &= 1,\\ %a_2 &= 2,\\ %a_3 &= 24,\\ a_n &= \frac{6a_{n-1}^2a_{n-3} - 8a_{n-1}a_{n-2}^2}{a_{n-2}a_{n-3}}, \qquad \text{pre } n > 3.\end{aligned}$$ Dokážte, že $n$ delí $a_n$ pre každé prirodzené číslo $n$.
KMS 08/09-Z1-13
Nápoveda 1
Najskôr upravte rekurentný vzťah do krajšieho tvaru.
Nápoveda 2
Použite substitúciu MATH_STASH_95_ENDSTASH. Dostanete tak postupnosť MATH_STASH_96_ENDSTASH s krajším rekurentným vyjadrením. Potom MATH_STASH_97_ENDSTASH.
Nápoveda 3
Pre postupnosť MATH_STASH_98_ENDSTASH máme MATH_STASH_99_ENDSTASH, MATH_STASH_100_ENDSTASH a MATH_STASH_101_ENDSTASH. Takúto postupnosť možno explicitne vyjadriť (pomocou štandardného postupu alebo aj tipnutím) ako MATH_STASH_102_ENDSTASH. Chceme tead ukázať, že MATH_STASH_103_ENDSTASH delí nejaké MATH_STASH_104_ENDSTASH pre MATH_STASH_105_ENDSTASH.
Nápoveda 4
Deliteľnosť vyplýva z Eulerovej vety, kde pre najväčšieho nepárneho deliteľa čísla MATH_STASH_106_ENDSTASH, označeného MATH_STASH_107_ENDSTASH, platí MATH_STASH_108_ENDSTASH. Deliteľnosť potrebnou mocninou dvojky je priama.
Úloha 8
Nech $(a\_n)\_{n=1}^\infty$ je postupnosť s počiatočnými členmi $a_1 = 1$, $a_2 = 4$, $a_3 = 15$ a s predpisom $$a_n = 15a_{n-2} - 4a_{n-3}\qquad \text{pre } n \ge 4.$$ Dokážte, že ak je $a_n$ prvočíslo, tak aj $n$ je prvočíslo.
KMS 05/06-Z3-11
Nápoveda 1
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 MATH_STASH_116_ENDSTASH je zložené číslo, tak MATH_STASH_117_ENDSTASH je tiež zložené. Akého deliteľa by MATH_STASH_118_ENDSTASH mohlo mať?
Nápoveda 2
Dokážte, že ak MATH_STASH_119_ENDSTASH, tak MATH_STASH_120_ENDSTASH. Aké vlastnosti tejto postupnosti by to mohli zaručiť?
Nápoveda 3
Všimnite si, že MATH_STASH_121_ENDSTASH. Nedal by sa takýto vzťah zovšeobecniť?
Nápoveda 4
Pre túto postupnosť platí MATH_STASH_122_ENDSTASH.
Nápoveda 5
Fixnite si MATH_STASH_123_ENDSTASH: to nám delí čísla MATH_STASH_124_ENDSTASH. Ukazujte teda induktívne, že MATH_STASH_125_ENDSTASH delí členy MATH_STASH_126_ENDSTASH.
Úloha 9
Postupnosť $(a\_n)\_{n=1}^\infty$ je definovaná rekurentne vzťahmi $$\begin{aligned} a_1 &= 20,\\ a_2 &= 30,\\ a_{n+2} &= 3a_{n+1}-a_n \text{ pre } n \geq 1.\end{aligned}$$ Nájdite všetky $n$, pre ktoré je $1+5a_n a_{n+1}$ štvorcom prirodzeného čísla.
KMS 09/10-L3-13
Nápoveda 1
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 MATH_STASH_131_ENDSTASH platí). Vypíšte si niekoľko prvých čísel postupnosti a skúmajte, medzi ktorými štvorcami sa MATH_STASH_132_ENDSTASH nachádza.
Nápoveda 2
Chceme nájsť také MATH_STASH_133_ENDSTASH, že MATH_STASH_134_ENDSTASH pre dostatočne veľké MATH_STASH_135_ENDSTASH. Vyskúšaním zistíme, že MATH_STASH_136_ENDSTASH (ale tu z druhej nerovnosti máme rovnosť a ým pádom riešenie), MATH_STASH_137_ENDSTASH, MATH_STASH_138_ENDSTASH, ... Čo za postupnosť je MATH_STASH_139_ENDSTASH? Ďalej existujú dve cesty: 1. Môžeme si všimnúť, že pre ňu platí rovnaký rekurentný predpis MATH_STASH_140_ENDSTASH. 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 MATH_STASH_141_ENDSTASH. Vyzerá v skutočnosti o niečo krajšie. Mimochodom, v oboch prípadoch nám stačí dokazovať, že MATH_STASH_142_ENDSTASH (teda pre MATH_STASH_143_ENDSTASH) bude pod najbližším väčším štvorcom.
Nápoveda 3
Všimnite si, že MATH_STASH_144_ENDSTASH. Chcete teda dokázať, že MATH_STASH_145_ENDSTASH.
Nápoveda 4
Tento dôkaz ide indukciou. Treba sa kus pohrať s vyjadrovaním a upravovaním výrazov. Rozpíšte si MATH_STASH_146_ENDSTASH cez rekurentný predpis, aby ste mohli využiť indukčný predpoklad.
