Matematyka.pl

P.S. Oczywiście wzór zwarty to: \(\displaystyle{ \sum_{i=1}^{n} \frac{2^i}{3^{2^i}+1} = \frac{3^{2^{n+1}}-1-2^{n+1}}{3^{2^{n+1}}-1}}\), powyższy zapis był tylko w celu przejrzystości dowodu

Brawo, a czy w tym coś nie przesunieto indeksów... bo dla n=1, wynik ma dac 2/10 a nie zbyt daje....?!

do 3 razy sztuka...?! A moze tam chodzi o
\(\displaystyle{ \sum_{k=1}^{n-1} \frac{k}{n+k} \; \frac{1}{2k-1} <4}\) ?! Co na to Exel?!

Tak tylko dla formalistów...(bo bylem ciekawy ile to jest) \(\displaystyle{ \frac{\sqrt{2}}{2}(2\sqrt{499}+\sqrt{1995}-1) \approx 62,467...}\)

Tak, było przesunięcie w indeksach. Teraz powinno być wszystko OK. Nauczka dla mnie, żeby nie zabierać się więcej za takie strasznie siłowe zadania, bo 0 pożytku z nich

Wydaje się, że jest OK, ale tak na prawdę raczej nie dowiemy się, jaki był oryginał tego zadania... Chyba, że tą informację dostaniemy od samego autora

Pomysł w miarę oczywisty (zbliżanie najbardziej oddalonych wyrazów), ale zapis już nie taki oczywisty. Niech \(\displaystyle{ k_1 \ge k_2 \ge \ldots k_n}\). Jeśli \(\displaystyle{ k_1-k_n \ge 2}\), to mamy:
\(\displaystyle{ k_1! \cdot k_n! > (k_1-1)! \cdot (k_n+1)! \iff k_1 > k_n+1}\). Zatem:
\(\displaystyle{ \prod_{i=1}^n k_i! > (k_1-1)! \cdot \prod_{i=2}^{n-1} k_i! \cdot (k_n+1)!}\)

Następnie sortujemy ciąg: \(\displaystyle{ (k_1-1,k_2,\ldots,k_n+1)}\) malejąco, czyli otrzymujemy znowu inny ciąg: \(\displaystyle{ k_1' \ge k_2' \ge \ldots \ge k_n'}\)

Operację tą kontynuujemy do takiego momentu, aż otrzymamy taki ciąg, że nie istnieją w nim dwie liczby różne od siebie o co najmniej 2 (jeśli różnica największego i najmniejszego wyrazu jest równa b, gdzie \(\displaystyle{ b \ge 2}\), to po nie więcej niż n takich operacjach (chyba nawet po mniejszej ilości, ale nie ma konieczności rozstrzygać tego) różnica największego i najmniejszego wyrazu będzie mniejsza od b).

Niech ten ostatni ciąg to \(\displaystyle{ (a_1,a_2,\ldots,a_n)}\) (posortowany malejąco, więc zgodnie z wcześniejszymi ustaleniami: \(\displaystyle{ a_n+1 \ge a_1 \ge a_2 \ge \ldots \ge a_n}\)). Oczywiście przy tych operacjach zachowana była suma liczb w ciągu. Zatem (nierówność nieostra, gdyż mogło być: \(\displaystyle{ k_i=a_i}\) dla i=1,2,...,n):
\(\displaystyle{ \prod_{i=1}^n k_i! \ge \prod_{i=1}^n a_i!}\)
Oczywiście: \(\displaystyle{ n(a_n+1)>(n-1)(1+a_n)+a_n \ge a_1+\ldots+a_{n-1}+a_n \ge n \cdot a_n}\), co oznacza: \(\displaystyle{ \left[ \frac{k_1+k_2+\ldots + k_n}{n} \right]=\left[ \frac{a_1+a_2+\ldots + a_n}{n} \right]=a_n}\). Zatem ponieważ: \(\displaystyle{ a_1 \ge \ldots \ge a_n}\), to:
\(\displaystyle{ \prod_{i=1}^n k_i! \ge \prod_{i=1}^n a_i! \ge \prod_{i=1}^n a_n! = (a_n!)^n=\left( \left[ \frac{k_1+k_2+\ldots + k_n}{n} \right] ! \right)^n}\)
Co należało dowieść.

Wykażemy dwa fakty:
I) Ciąg reszt z dzielenia przez 2 wyrazów tego ciągu to: \(\displaystyle{ (1,0,1,1,0,1,1,0,\ldots)}\), czyli parzyste są jedynie wyrazy o numerach 3k+2
II) Ciąg reszt z dzielenia przez 3 wyrazów tego ciągu to: \(\displaystyle{ (1,2,1,2,\ldots)}\).

ad I)
Wystarczy wykazać, że jeśli pewien wyraz jest parzysty, to dwa następne będą nieparzyste, a po nich następuje znowu jeden wyraz parzysty, itd. Wynika to wprost ze wzoru rekurencyjnego. Proste jak drut więc dowód pomijam.

ad II)
Tu jest troszkę trudniej, ale nadal dowód banalny. Należy policzyć (mod 3) wyrazy od 3 do 8, a następnie zauważyć, że: \(\displaystyle{ i \ge 7 \Rightarrow a_{i} \equiv a_{i-6} \ (mod \ 3)}\) (częściowo wynika z I), i to dowieść indukcją. Również proste jak drut.

Wróćmy do zadania. Jeśli by było \(\displaystyle{ a_n=0}\), to \(\displaystyle{ a_n \equiv 0 \ (mod \ 3)}\), co na mocy II jest niemożliwe. Sprzeczność kończy dowód.

Niech \(\displaystyle{ y=\frac{1}{x}}\). Wówczas po podstawieniu i zwinięciu otrzymujemy równość: \(\displaystyle{ (f(x)-f(\frac{1}{x})) \cdot (f(x)+f(\frac{1}{x})-1) = 0}\). Niech x będzie takie, że \(\displaystyle{ f(x)=\frac{1}{2}}\) (zgodnie z założeniami zadania takowe istnieje). Wówczas:
\(\displaystyle{ f(\frac{1}{x})=f(x) \vee f(\frac{1}{x})=1-f(x)}\) - w obu przypadkach otrzymujemy \(\displaystyle{ f(\frac{1}{x})=\frac{1}{2}}\).

Zatem udowodniliśmy: \(\displaystyle{ f(x)=\frac{1}{2} \Rightarrow f(\frac{1}{x})=\frac{1}{2}}\)

Teraz niech y będzie takie, że \(\displaystyle{ f(y)=\frac{1}{2}}\), oczywiście zgodnie z powyższym \(\displaystyle{ f(\frac{1}{y})=\frac{1}{2}}\). Czyli:
\(\displaystyle{ f(x)-\frac{1}{2}=f(x) \cdot \frac{1}{2} - f(\frac{1}{x}) \cdot \frac{1}{2} \Rightarrow f(x)+f(\frac{1}{x})=1}\)

Podstawiając \(\displaystyle{ x=-1}\) otrzymujemy: \(\displaystyle{ 2f(-1)=1 \iff f(-1)=\frac{1}{2}}\).

Odpowiedź: \(\displaystyle{ f(-1)=\frac{1}{2}}\).

Rozważmy dla wygody ciągi \(\displaystyle{ a_{n} = \frac{1}{x_{n}}}\) oraz \(\displaystyle{ b_{n} = \frac{1}{y_{n}}}\). Mamy wtedy:
\(\displaystyle{ a_{n+1} = \frac{a_{n} + b_{n}}{2} \\
b_{n+1} = \sqrt{a_{n+1} b_{n}}}\)
Mamy zatem:
\(\displaystyle{ a_{n} = \frac{b_{n}^2}{b_{n-1}}}\)
Stąd:
\(\displaystyle{ b_{n+1} = \sqrt{ \frac{b_{n} + \frac{b_{n}^2}{b_{n-1}}}{2} \cdot b_{n}} \\
\frac{b_{n+1}}{b_{n}} = \sqrt{\frac{1+ \frac{b_{n}}{b_{n-1}}}{2}} \\
c_{n} = \frac{b_{n+1}}{b_{n}} \\
c_{0} = \frac{\sqrt{3}}{2} \\
c_{n} = \sqrt{\frac{1+c_{n-1}}{2}}}\)
W tym wzorze rozpoznajemy wzór na cosinus kąta połówkowego, zatem:
\(\displaystyle{ c_{n} = cos(\frac{\pi}{6\cdot 2^{n}})}\)
Następnie:
\(\displaystyle{ b_{n+1} = c_{n} b_{n} \Rightarrow b_{n+1} = b_{0} \cdot \prod_{k=0}^{n}c_{k} = \prod_{k=0}^{n} cos(\frac{\pi}{6\cdot2^{k}} \rightarrow \frac{sin(\frac{\pi}{3})}{\frac{\pi}{3}}}\)
Zatem oczywiście:
\(\displaystyle{ y_{n} \rightarrow \frac{\frac{\pi}{3}}{sin\frac{\pi}{3}}}\)
Sprawdzenie, że \(\displaystyle{ x_{n}}\) dąży do tej samej granicy to jedynie prosta formalność.

Oczywiście wystarczy pokazać, że \(\displaystyle{ \sum_{i=1}^{100} \frac{1}{\sqrt{i}} <20}\)

Gdy \(\displaystyle{ i \ge 1}\), to tworzymy taki oto lemat: \(\displaystyle{ \frac{1}{\sqrt{i}} < 2\sqrt{i} - 2\sqrt{i-1}}\)

Jest to równoważne: \(\displaystyle{ 1<2i-2\sqrt{i^2-i} \iff 2\sqrt{i^2-i}<2i-1 \iff 4i^2-4i<4i^2-4i+1 \iff 0<1}\), czyli prawda.

Dodając lematy dla i=1,2,...,100, otrzymujemy: \(\displaystyle{ \sum_{i=1}^{100} \frac{1}{\sqrt{i}} < 2\sqrt{100} - 2\sqrt{1-1} = 20}\), co należało dowieść.

P.S. Ten lemat to inaczej \(\displaystyle{ \frac{1}{\sqrt{i}} < \int_{i-1}^{i} \frac{1}{\sqrt{x}} dx}\), więc nie wziąłem go "z kapelusza", choć pewnie taki był zamysł autora . Po prostu chciałem przedstawić elementarne rozwiązanie bez całek.

Niech: \(\displaystyle{ x=\sin^2 \alpha, \ y=\sin^2 \beta}\), gdzie (zgodnie z dziedziną równania): \(\displaystyle{ 0 \le x \le 1, \ 0<y<1}\).

Pokażemy, że przy takich warunkach zachodzi: \(\displaystyle{ \frac{x^{k+1}}{y^k}+\frac{(1-x)^{k+1}}{(1-y)^k} \ge 1}\), przy czym równość jest wtedy i tylko wtedy, gdy \(\displaystyle{ x=y}\).

Gdy \(\displaystyle{ k=1}\), to wystarczy użyć nierówności Cauchy'ego-Schwarza w formie Engela: \(\displaystyle{ \frac{x^2}{y}+\frac{(1-x)^2}{1-y} \ge \frac{(x+(1-x))^2}{y+(1-y)}=\frac{1^2}{1}=1}\), przy czym równość zachodzi dokładnie wtedy, gdy: \(\displaystyle{ \frac{x}{y}=\frac{1-x}{1-y}}\), czyli: \(\displaystyle{ x=y}\).

Teraz niech \(\displaystyle{ k \ge 2}\) i niech \(\displaystyle{ f(x)=x^k}\). Wówczas \(\displaystyle{ f''(x)=k(k-1)x^{k-2}>0}\), zatem z nierówności Jensena (ładnie się składa, że wagami są \(\displaystyle{ x}\) oraz \(\displaystyle{ 1-x}\)) dostajemy:
\(\displaystyle{ \frac{x^{k+1}}{y^k}+\frac{(1-x)^{k+1}}{(1-y)^k} = x \cdot f(\frac{x}{y}) + (1-x) + f(\frac{1-x}{1-y}) \ge \\ \ge f(x \cdot \frac{x}{y} + (1-x) \cdot \frac{1-x}{1-y}) = (\frac{x^2}{y}+\frac{(1-x)^2}{1-y})^k \ge \\ \ge 1^k = 1}\)
Ostatnia nierówność oczywiście z rozpatrzonego wcześniej przypadku. Równość otrzymujemy, gdy w obu przedstawionych nierównościach (Jensena i Cauchy'ego-Schwarza w formie Engela) także zachodzi równość, a to następuje, gdy \(\displaystyle{ x=y}\).

Wróćmy do zadania. Z powyższego rozumowania i warunków zadania wynika, że \(\displaystyle{ S_k=1 \Rightarrow x=y}\). Ale to oznacza, że dla każdego n naturalnego:
\(\displaystyle{ S_n=\frac{x^{n+1}}{y^n}+\frac{(1-x)^{n+1}}{(1-y)^n}=\frac{x^{n+1}}{x^n}+\frac{(1-x)^{n+1}}{(1-x)^n}=x + (1-x) = 1}\)

Co należało dowieść.

Gdy n=1 to odrzucamy, bo \(\displaystyle{ f(x)=10(x-0,9)}\), tj \(\displaystyle{ f(0,5)=-4}\)

Gdy n=2 f (o ile istnieje) ma postać \(\displaystyle{ f(x)=a(x-0,9)(x- 1+ \frac{10}{a})}\) Jednak wtedy \(\displaystyle{ 0 \geq f(0)=-9+9a}\) skad \(\displaystyle{ a \leq 1}\)
Z drugiej strony \(\displaystyle{ f(0,5)= -4 +\frac{4}{5}a \geq -0,1}\) co daje \(\displaystyle{ a \geq 19,5}\) sprzecznosc

Gdy n=3 oczywiscie nieco sie komplikuje
f (o ile istnieje) ma postać \(\displaystyle{ f(x)=a(x-0,9)(x^2+bx+ \frac{10}{a}-1-b)}\)

Warunki \(\displaystyle{ 0 \geq f(0) \geq -0,1}\)
\(\displaystyle{ 0 \geq f(0,5) \geq -0,1}\)

prowadza do ukladu nierównosci:
\(\displaystyle{ \begin{cases} 10 \geq a+ab \geq \frac{89}{9}\\40 \geq 3a+2ab \geq 39\end{cases}}\)

Wydaje mi sie iz nie ma on realizacji (chwilowo tego niezbyt widze)
postaram sie uzupełnic, (moze ktos pomoze?!)

szkic Istnieje liczba naturalna \(\displaystyle{ m}\), t ze \(\displaystyle{ 2^{n+1} \geq (\frac{3}{2})^m \geq 2^n}\) Wtedy kładziemy \(\displaystyle{ x=\sqrt[m]{2}}\)

Ten układ chyba ma realizację, ale masz jeszcze do wykorzystania resztę przedziału \(\displaystyle{ <0; \ 0,9>}\). Zadanie typowo na umęczenie.

Idea raczej jasna - niech \(\displaystyle{ a=\sum_{i=1}^{100} \frac{100!}{i}}\) oraz \(\displaystyle{ b=100!}\). Wystarczy pokazać, że przy rozkładzie liczb \(\displaystyle{ a, b}\) na czynniki pierwsze w obu tych liczbach piątka występuje w tej samej potędze. Zapis już nie będzie taki ekspresowy

Oczywiście w liczbie \(\displaystyle{ b}\) piątka występuje w potędze: \(\displaystyle{ \sum_{i=1}^\infty \left[ \frac{100}{i} \right] = \left[ \frac{100}{5} \right] + \left[ \frac{100}{25} \right] = 24}\)

Podzielmy liczbę \(\displaystyle{ a}\) na sumę trzech sum:

I) \(\displaystyle{ a_1=\sum_{1 \le i \le 100 \ \wedge \ 5 \nmid i} \frac{100!}{i}}\)

II) \(\displaystyle{ a_2=\sum_{1 \le i \le 100 \ \wedge \ 5|i \ \wedge \ 25 \nmid i} \frac{100!}{i}}\)

III) \(\displaystyle{ a_3=\sum_{1 \le i \le 100 \ \wedge \ 25|i} \frac{100!}{i}}\)

Często będę używał pewnego faktu, o którym wypada wspomnieć. Jeśli liczba \(\displaystyle{ \frac{x}{y}}\) jest całkowita oraz liczby \(\displaystyle{ x, y}\) są względnie pierwsze z \(\displaystyle{ k}\), to:
* w zbiorze \(\displaystyle{ \lbrace 1,\ldots,k-1 \rbrace}\) zawsze istnieje dokładnie jedna taka liczba \(\displaystyle{ z}\), że: \(\displaystyle{ yz \equiv 1 \ (mod \ k)}\) ; liczbę \(\displaystyle{ z}\) będę oznaczał jako \(\displaystyle{ y^{-1}}\) (coś a'la odwrotność); oczywiście \(\displaystyle{ z}\) też jest względnie pierwsza z \(\displaystyle{ k}\) ; oczywiście także: \(\displaystyle{ y^{-1} = (y+tk)^{-1}}\)
* \(\displaystyle{ \frac{x}{y} \equiv xz \ (mod \ k)}\)

Dowód tych faktów zostawiam chętnym, podpowiem, że jest on prosty i intuicyjny

Niech \(\displaystyle{ p=(1 \cdot 2 \cdot 3 \cdot 4)^3 \cdot (6 \cdot 7 \cdot 8 \cdot 9)^2 \cdot \ldots \cdot (16 \cdot 17 \cdot 18 \cdot 19)^2 \cdot (21 \cdot 22 \cdot 23 \cdot 24) \cdot \ldots \cdot (96 \cdot 97 \cdot 98 \cdot 99)}\)
Nie jest trudno zauważyć, że \(\displaystyle{ 100!=5^{24} \cdot p}\).

Pokażemy, że: \(\displaystyle{ 5^{25}|a_1, \ 5^{25}|a_2, \ 5^{24}|a_3, \ 5^{25} \nmid a_3}\), co zakończy dowód zadania.

Więc:
I) Rozpatrzmy \(\displaystyle{ a_1}\). Liczby \(\displaystyle{ \frac{p}{i}}\) są całkowite, więc:
\(\displaystyle{ a_1=5^{24} \cdot (\sum_{1 \le i \le 100 \ \wedge \ 5 \nmid i} \frac{p}{i})}\)
Pokażemy, że suma w nawiasie jest podzielna przez 5:
\(\displaystyle{ \sum_{1 \le i \le 100 \ \wedge \ 5 \nmid i} \frac{p}{i} \equiv p \cdot \sum_{1 \le i \le 100 \ \wedge \ 5 \nmid i} i^{-1} = p \cdot 20 \sum_{i=1}^4 i^{-1} \equiv 0 \ (mod \ 5)}\)

II) Rozpatrzmy \(\displaystyle{ a_2}\). Liczby \(\displaystyle{ \frac{p}{\frac{i}{5}}}\) są całkowite, więc:
\(\displaystyle{ a_2=5^{23} \cdot (\sum_{1 \le i \le 100 \ \wedge \ 5|i \ \wedge \ 25 \nmid i} \frac{p}{\frac{i}{5}})}\)
Pokażemy, że suma w nawiasie jest podzielna przez 25. Tu będzie troszkę trudniej, ale postąpimy troszkę sprytniej - chętnym zostawiam przemyślenie tej równości zbiorów: \(\displaystyle{ \lbrace 1^{-1}, 2^{-1}, 3^{-1}, 4^{-1}, 6^{-1}, \ldots , 24^{-1} \rbrace = \lbrace 1, 2, 3, 4, 6, \ldots , 24 \rbrace}\), czyli:
\(\displaystyle{ \sum_{1 \le i \le 100 \ \wedge \ 5|i \ \wedge \ 25 \nmid i} \frac{p}{\frac{i}{5}} \equiv \\ \equiv p \cdot (1^{-1} + 2^{-1} + 3^{-1} + 4^{-1} + 6^{-1} + \ldots + 24^{-1} - 21^{-1} - 22^{-1} - 23^{-1} - 24^{-1}) = \\ = p \cdot (10+30+50+70+90-6-8-12-24)= p \cdot 200 \equiv 0 \ (mod \ 25)}\)

III) \(\displaystyle{ a_3=5^{22} \cdot (\frac{p}{1} + \frac{p}{2} + \frac{p}{3} + \frac{p}{4})}\)
Rozpatrzmy ten nawias modulo \(\displaystyle{ 5^3=125}\):

\(\displaystyle{ \frac{p}{1} + \frac{p}{2} + \frac{p}{3} + \frac{p}{4} \equiv p \cdot (1^{-1} + 2^{-1}+ 3^{-1} + 4^{-1}) = \\ = p \cdot (1+63+42+94)= p \cdot 200 \equiv 25 \cdot 8p}\)

Ponieważ \(\displaystyle{ 5 \nmid 8p}\), to ten nawias jest podzielny przez 25, a nie jest podzielny przez 125. Zatem: \(\displaystyle{ 5^{24}|a_3 \ \wedge \ 5^{25} \nmid a_3}\).

Podsumowując: \(\displaystyle{ 5^{24}|a \ \wedge \ 5^{25} \nmid a}\), co należało dowieść

Gdy \(\displaystyle{ n=1}\) to chyba nie trzeba mówić czemu ta nierówność jest prawdziwa.

Niech \(\displaystyle{ a_i}\) oznaczają wszystkie po kolei składniki tej sumy znajdującej się po lewej stronie (składającej się z \(\displaystyle{ 2^n}\) składników), oczywiście \(\displaystyle{ a_i \ge 0}\). Gdy \(\displaystyle{ n \ge 2}\) korzystamy z nierówności pomiędzy średnią arytmetyczną a geometryczną:
\(\displaystyle{ \frac{\sum_{i=1}^{2^n} a_i}{2^n} \le \sqrt{ \frac{ \sum_{i=1}^{2^n} a_i^2 }{2^n} }}\)

Oczywiście \(\displaystyle{ a_i^2 = (x_1^2+\ldots+x_n^2) + 2 (\sum_{1 \le j<k \le n} \epsilon_j \epsilon_k x_j x_k)}\)

Dla każdych takich \(\displaystyle{ j,k}\) w dokładnie \(\displaystyle{ 2^{n-1}}\) wyrazach spośród \(\displaystyle{ a_i}\) mamy \(\displaystyle{ \epsilon_j = \epsilon_k}\) oraz w dokładnie \(\displaystyle{ 2^{n-1}}\) wyrazach spośród \(\displaystyle{ a_i}\) mamy \(\displaystyle{ \epsilon_j = - \epsilon_k}\). Zatem:
\(\displaystyle{ \sum_{a_i} \epsilon_j \epsilon_k x_j x_k = 2^{n-1} x_j x_k - 2^{n-1} x_j x_k =0}\)

Co za tym idzie: \(\displaystyle{ \sum a_i^2 = (x_1^2+\ldots+x_n^2) + 2 (\sum_{1 \le j<k \le n} \epsilon_j \epsilon_k x_j x_k)= \sum 1 + 2 \cdot 0 = 2^n}\)

Czyli: \(\displaystyle{ \sum_{i=1}^{2^n} a_i \le 2^n \cdot \sqrt{ \frac{ \sum_{i=1}^{2^n} a_i^2 }{2^n} }= 2^n \sqrt{\frac{2^n}{2^n}} = 2^n}\), co należało dowieść.

Najpierw trzeba udowodnić, że: \(\displaystyle{ p< \frac{p^{n+1}-n}{p^n-n} \le p+1}\) (proste wymożenie i uporządkowanie), zatem: \(\displaystyle{ \left( \frac{p^{n+1}-n}{p^n-n} \right]=p+1=\frac{p^2-1}{p-1}}\)

Teraz indukcyjnie udowodnimy, że dla \(\displaystyle{ k=0,1,\ldots,n-1}\):
\(\displaystyle{ \left( \frac{p^{n+1}-(n-k)}{p^n-(n-k)}\cdot \ldots \cdot \left( \ldots \left( \frac{p^{n+1}-n}{p^n-n} \right] \ldots \right] \right]=\frac{p^{k+2}-1}{p-1}}\)

Założenie indukcyjne (zarazem tezę dla n=1) już udowodniliśmy, w kroku indukcyjnym zostaje udowodnić, że:
\(\displaystyle{ \frac{p^{k+2}-1}{p-1}-1 < \frac{p^{n+1}-(n-k)}{p^n-(n-k)} \cdot \frac{p^{k+1}-1}{p-1} \le \frac{p^{k+2}-1}{p-1}}\)

--

Lewa nierówność to inaczej:
\(\displaystyle{ (p^{k+2}-p) \cdot (p^n-(n-k))<(p^{n+1}-(n-k)) \cdot (p^{k+1}-1)}\)

Po wymnożeniu i uporządkowaniu:
\(\displaystyle{ (p-1)(n-k)<p^{k+1}(p-1)(n-k)}\)

Co jest równoważne: \(\displaystyle{ 1<p^{k+1}}\)

Co jest oczywiście prawdą, bo \(\displaystyle{ p \ge 2}\) oraz \(\displaystyle{ k+1 \ge 1}\).

--

Za to prawa nierówność jest równoważna:
\(\displaystyle{ (p^{k+2}-1) \cdot (p^n-(n-k)) \ge (p^{n+1}-(n-k)) \cdot (p^{k+1}-1)}\)

Po wymnożeniu i uporządkowaniu:
\(\displaystyle{ p^n(p-1) \ge (n-k)p^{k+1}(p-1)}\)

Co jest równoważne: \(\displaystyle{ p^{n-k-1} \ge n-k}\)

Tu można np. indukcyjnie udowodnić, że dla \(\displaystyle{ 1 \le x, \ x \in \mathbb{Z}}\) mamy: \(\displaystyle{ x \le 2^{x-1}}\), co zakończy dowód tej nierówności, gdyż: \(\displaystyle{ 2^{x-1} \le p^{x-1}}\).

Dowód tych dwóch nierówności został zakończony.

Kładąc: \(\displaystyle{ k=n-1}\) dostaniemy:
\(\displaystyle{ \left( \frac{p^{n+1}-1}{p^n-1}\cdot \left( \frac{p^{n+1}-2}{p^n-2} \cdot \left( \ldots \left( \frac{p^{n+1}-n}{p^n-n} \right] \ldots \right] \right] \right]=\frac{p^{n+1}-1}{p-1}}\)

Co należało dowieść

Rozważmy sumę
\(\displaystyle{ \sum_{k=0}^{\infty} {n-k \choose k} x_{0}^{k} = f_{n}(x_{0})}\).
Wobec równości \(\displaystyle{ {n-k \choose k} = {(n-1) - k \choose k} + {(n-2) - (k-1) \choose k-1}}\)
otrzymujemy zależność rekurencyjną na \(\displaystyle{ f_{n}(x_{0})}\):
\(\displaystyle{ f_{n}(x_{0}) = f_{n-1}(x_{0}) + x_{0} f_{n-2}(x_{0})}\).
W szczególności suma z zadania równa się \(\displaystyle{ f_{n}(-\frac{1}{4})}\), a z otrzymanej zależności można łatwo indukcyjnie udowodnić, że:
\(\displaystyle{ f_{n}(-\frac{1}{4}) = \frac{n+1}{2^{n}}}\).
Możliwe, że korzystając z tej zależności rekurencyjnej da się rozwiązać zadanie 55.

Można zacząć od udowodnienia tego, że dokładnie co drugi wyraz ciągu jest parzysty (poczynając od zerowego), czyli: \(\displaystyle{ 2^1|a_n \iff 2^1|n}\). Niech to będzie nasze założenie indukcyjne (oczywiście trzeba to udowodnić, ale że to proste jak 2+2, to pozwolę sobie opuścić dowód). Oczywiście \(\displaystyle{ a_0}\) spełnia warunki zadania, więc pominiemy go przy dalszych rozważaniach

Mamy: \(\displaystyle{ a_2=2, \ a_3=5, \ a_4=12}\), itd. Rozpisując wzór rekurencyjny możemy zauważyć:
\(\displaystyle{ a_n=2a_{n-1}+a_{n-2}=2(2a_{n-2}+a_{n-3})+a_{n-2} = 5a_{n-2}+2a_{n-3}=a_3a_{n-2}+a_2a_{n-3}}\)

Łatwo zauważyć, że rozpisując tak dalej otrzymamy (można np. zastosować indukcję): \(\displaystyle{ a_n=a_{i+1}a_{n-i} + a_i a_{n-i-1}}\) dla i=1,2,...,n-1. Ten wzór bardzo nam się przyda do rozwiązania zadania.

Założenie indukcyjne można zapisać w ten sposób: dla każdego \(\displaystyle{ k}\) naturalnego takiego, że: \(\displaystyle{ 1 \le k<t}\), \(\displaystyle{ t \ge 2}\), zachodzi: \(\displaystyle{ 2^k|a_n \iff 2^k|n}\)

Teraz udowodnimy dwie implikacje:
I) \(\displaystyle{ 2^t|n \Rightarrow 2^t|a_n}\)
II) \(\displaystyle{ 2^t|a_n \Rightarrow 2^t|n}\)

Co będzie naszym krokiem indukcyjnym.

I) Mamy: \(\displaystyle{ n=b \cdot 2^t}\). Niech \(\displaystyle{ i=b \cdot 2^{t-1}}\). Wówczas:
\(\displaystyle{ a_n=a_{b \cdot 2^{t-1}+1}a_{b \cdot 2^{t-1}} + a_{b \cdot 2^{t-1}} a_{b \cdot 2^{t-1}-1} \right) = a_{b \cdot 2^{t-1}} \cdot (a_{b \cdot 2^{t-1}+1}+a_{b \cdot 2^{t-1}-1})}\)
Oczywiście z założenia: \(\displaystyle{ 2^{t-1}|a_{b \cdot 2^{t-1}}}\) oraz oba składniki w ostatnim nawiasie są nieparzyste (bo indeksy są niepodzielne przez 2 i korzystamy z założenia indukcyjnego), zatem nawias jest podzielny przez 2. Co za tym idzie całość jest podzielna przez \(\displaystyle{ 2^{t-1} \cdot 2 = 2^t}\), czyli: \(\displaystyle{ 2^t|a_n}\), co kończy dowód tej implikacji.

II) Niech \(\displaystyle{ n=2^t \cdot b + c}\), gdzie \(\displaystyle{ 0 \le c < 2^t}\). Niech \(\displaystyle{ i=2^t \cdot b}\). Wówczas:
(*) \(\displaystyle{ 2^t|a_n=a_{2^t \cdot b + 1} \cdot a_c + a_{2^t \cdot b} \cdot a_{c-1}}\)
Oczywiście z implikacji I) mamy: \(\displaystyle{ 2^t|a_{2^t \cdot b}}\), zatem podzielność (*) zachodzi wtedy i tylko wtedy, gdy:
(**) \(\displaystyle{ 2^t|a_{2^t \cdot b + 1} \cdot a_c}\)
Ale \(\displaystyle{ a_{2^t \cdot b + 1}}\) jest nieparzyste, bo indeks jest niepodzielny przez 2 i korzystamy z założenia indukcyjnego. Zatem podzielność (**) zachodzi wtedy i tylko wtedy, gdy:
\(\displaystyle{ 2^t|a_c}\)

Pokażemy, że \(\displaystyle{ c=0}\). Przypuśćmy, że tak nie jest.

a) \(\displaystyle{ c=2^d \cdot e}\), gdzie \(\displaystyle{ d \le t-2}\) oraz e jest nieparzyste (czyli nie rozpatrujemy tylko przypadku \(\displaystyle{ c=2^{t-1}}\))

Wówczas gdyby było: \(\displaystyle{ 2^t|a_c}\), to także: \(\displaystyle{ 2^{d+1}|a_c}\), a skoro \(\displaystyle{ d+1<t}\), to z założenia indukcyjnego: \(\displaystyle{ 2^{d+1}|a_c \Rightarrow 2^{d+1}|c=2^d \cdot e}\) - sprzeczność, bo e jest nieparzyste

b) \(\displaystyle{ c=2^{t-1}}\). Gdy t=2 to można na palcach policzyć, że mamy sprzeczność, bo \(\displaystyle{ 2^2 \nmid 2}\). Gdy \(\displaystyle{ t>3}\), to niech: \(\displaystyle{ i=2^{t-2}}\) i wówczas:
\(\displaystyle{ 2^t|a_c=a_{2^{t-2}+1} \cdot a_{2^{t-2}} + a_{2^{t-2}} \cdot a_{2^{t-2}-1}=a_{2^{t-2}} \cdot ( a_{2^{t-2}+1} + a_{2^{t-2}-1} )}\)

Pokażemy jeszcze drobny fakt - każdy wyraz tego ciągu o nieparzystym indeksie przystaje do 1 modulo 4, gdyż: \(\displaystyle{ 2|a_{2f}}\), czyli: \(\displaystyle{ a_{2f+1}-a_{2f-1}=2a_{2f} =4g \equiv 0 \ (mod \ 4)}\), czyli każde dwa kolejne nieparzyste wyrazy tego ciągu dają tą samą resztę w dzieleniu przez 4, co za tym idzie jest ona stała i równa \(\displaystyle{ a_1 \ (mod \ 4)}\), czyli 1.

Zatem: \(\displaystyle{ ( a_{2^{t-2}+1} + a_{2^{t-2}-1} ) \equiv 1+1 \equiv 2 \ (mod \ 4)}\) oraz: \(\displaystyle{ 2^{t-2}|a_{2^{t-2}} \wedge 2^{t-1} \nmid a_{2^{t-2}}}\), czyli: \(\displaystyle{ 2^{t-1}|a_c \wedge 2^t \nmid a_c}\) - zatem i tutaj \(\displaystyle{ 2^t \nmid a_c}\)

Przypuszczenie, że \(\displaystyle{ c \neq 0}\) poprowadziło nas do błędnych wniosków. Więc \(\displaystyle{ c=0}\), dalej: \(\displaystyle{ n=2^t \cdot b}\), co kończy dowód implikacji II) i zarazem potwierdza tezę zadania.

Niech \(\displaystyle{ \sigma(k)}\) oznacza liczbę dzielników \(\displaystyle{ k}\).
Mamy udowodnić, że:

\(\displaystyle{ \sum_{d|n} \sigma(d)^3 = (\sum_{d|n} \sigma(d))^2}\)

Dla \(\displaystyle{ n=1}\) teza wygląda na prawdziwą. Użyjmy teraz indukcji matematycznej: załóżmy, że mamy tezę dla wszystkich liczb naturalnych mniejszych od \(\displaystyle{ n}\) i pokażmy ją dla \(\displaystyle{ n}\).
Jeśli \(\displaystyle{ n = p^k}\), to dzielnikami \(\displaystyle{ n}\) są \(\displaystyle{ 1, p, p^2, ..., p^k}\). Funkcja \(\displaystyle{ \sigma}\) jest dla nich równa odpowiednio \(\displaystyle{ 1, 2, \ldots, k+1}\) i nasza równość wynika z bardzo znanego faktu:
\(\displaystyle{ \sum_{j=1}^{k+1}j^3 = (\sum_{j=1}^{k+1}j)^2}\)

Jeśli zaś \(\displaystyle{ n}\) ma co najmniej dwa dzielniki pierwsze, to można przedstawić \(\displaystyle{ n}\) jako \(\displaystyle{ r \cdot s}\), gdzie \(\displaystyle{ r}\) i \(\displaystyle{ s}\) są względnie pierwsze i mniejsze od \(\displaystyle{ n}\). Dzielniki \(\displaystyle{ n}\) to liczby postaci \(\displaystyle{ r' s'}\), gdzie \(\displaystyle{ r' | r}\), \(\displaystyle{ s' | s}\). Z podobnych powodów (dzielniki \(\displaystyle{ r's'}\) są iloczynami dzielników \(\displaystyle{ r'}\) i \(\displaystyle{ s'}\)) dostajemy \(\displaystyle{ \sigma(r' s') = \sigma(r')\sigma(s')}\). Wiedząc z założenia indukcyjnego, że dla \(\displaystyle{ r}\) i \(\displaystyle{ s}\) teza jest prawdziwa, możemy napisać:

\(\displaystyle{ \sum_{d|n} \sigma(d)^3 = \sum_{r'|r, s'|s} \sigma(r' s')^3 = \sum_{r'|r, s'|s} \sigma(r')^3 \sigma(s')^3 = \sum_{r'|r} \sigma(r')^3 \sum_{s'|s} \sigma(s')^3 = (\sum_{r'|r} \sigma(r'))^2 (\sum_{s'|s} \sigma(s'))^2 = (\sum_{r'|r} \sigma(r') \sum_{s'|s} \sigma(s'))^2 = (\sum_{r'|r, s'|s} \sigma(r' s'))^2 = (\sum_{d|n} \sigma(d))^2}\)

Voilà.

Niech \(\displaystyle{ L_k= 1^m+2^m+....+(n^k)^m}\). Indukcja po k. \(\displaystyle{ L_1=1}\) wiec ok, Niech \(\displaystyle{ L_k}\) jest podzielne przez \(\displaystyle{ n^{k-1}}\) mamy
\(\displaystyle{ L_{k+1}=L_k +\sum_{j=1...,n-1 \ i=1,...,n^k} (jn^k+i)^m= L_k +\sum_{j=1...,n-1 \ i=1,...,n^k} i^m +A_{i,j}n^k}\) gdzie \(\displaystyle{ A_{i,j}}\) sa to l naturalne,
tj \(\displaystyle{ L_{k+1}=L_k +\sum_{j=1}^{n-1} L_k+B_j n^k =nL_k +n^k(B_1+...+B_{n-1})}\) , gdzie \(\displaystyle{ B_{j}=A_{1,j}+...+A_{n^k,j}}\)
Liczba ta dzieki zalozeniu indukcyjnemu dzieli sie przez \(\displaystyle{ n^k}\) cbdo

Jesli \(\displaystyle{ a_n=2^km}\) k>0, m liczba nieparzysta, to \(\displaystyle{ a_{n+k}=3^km}\) liczba nieparzysta, tj w ciagu tym liczb jest nieskonczenie wiele liczb nieparzystych

Być moze w zadaniu chiodzilo o
Znalezc wszystkie pary liczb pierwszych \(\displaystyle{ (p,q)}\) takie ze \(\displaystyle{ (p+1)^q -1}\) jest potega liczby naturalnej o wykladniku >1 (w tej wersji zadanie przewija sie w roznych żródłach... ), w wersji jaka tu -jest raczej zbyt proste...

Przedstawie tylko szkic rozwiązania, jeśli ktoś chce, to, tak myślę, z łatwością odtworzy to co pominąłęm.

Pomysł polega na tym aby w jakiś sposób wydobyć zależność rekurencyjną dla sum \(\displaystyle{ S_n= \sum_{k=1}^{n} {n \choose n+k} k^2}\). Z pomocą przychodzi dobrze znana własność symbolu Newtona:
\(\displaystyle{ {n \choose k}=\begin{cases} {n-1 \choose k}+ {n-1 \choose k-1},\ 0<k<n \\
1,\ k=0,\ k=n
\end{cases}}\)
Zastosujmy ją dwukrotnie do symbolu Newtona w \(\displaystyle{ S_n}\). Po różnych przekształceniach, które tutaj pominę, otrzymujemy:
\(\displaystyle{ S_n=4S_{n-1}+ {2n-2 \choose n-1}+2\sum_{k=1}^{n-1} {2n-2 \choose n-1+k}}\) (*),
obliczmy sumę \(\displaystyle{ \sum_{k=1}^{n} {n \choose n+k}}\). Korzystając z faktu, że \(\displaystyle{ {n \choose k} = {n \choose n-k}}\) dostajemy, że:
\(\displaystyle{ 2^{2n} = \sum_{k=0}^{n-1} {2n \choose k} + {2n \choose n} +
\sum_{k=1}^{n} {2n \choose n+k}={2n \choose n}+2\sum_{k=1}^{n} {2n \choose n+k}}\)
a więc (z (*)) mamy rekurencję:
\(\displaystyle{ S_n=4S_{n-1}+2^{2n-2}}\). Po uzupełnieniu jej o warunek początkowy \(\displaystyle{ S_1=1}\) i rozwiązaniu dostajemy tezę.

Permutacje o postulowanej własnosci zwiemy dobra. Jest jasne, ze skoro \(\displaystyle{ a_{n-1}-a_n}\) dzieli sie przez \(\displaystyle{ n-1}\), wiec ostatnie dwa miejsca zajmować musza w permutacji dobrej \(\displaystyle{ 1}\) i \(\displaystyle{ n}\). Permutacje konczace sie na \(\displaystyle{ n}\) zwiemy typu a, zas konczace sie na \(\displaystyle{ 1}\) typu b.

Jesli \(\displaystyle{ (a_1, ...a_n)}\) jest dobra typu a, to \(\displaystyle{ (a_1, ...,a_{n-1})}\) jest dobra typu b zbioru \(\displaystyle{ \{1,..,n-1 \}}\).
Jesli \(\displaystyle{ (a_1, ..., a_n)}\) jest dobra typu b, to \(\displaystyle{ (a_1-1, ...a_{n-1}-1)}\) jest dobra typu a zbioru \(\displaystyle{ \{1,..., n-1 \}}\) .
Istnieje wiec bijekcja miedzy zbiorem permutacji \(\displaystyle{ n}\) elementowych dobrych a zbiorem permutacji \(\displaystyle{ n-1}\) elementowych dobrych. Jest ich tyle samo.
Skoro dla permutacji \(\displaystyle{ n=3}\) sa dwie takie: \(\displaystyle{ 2, 1, 3}\) i \(\displaystyle{ 2, 3, 1}\), wiec dla dowolnego \(\displaystyle{ n}\) sa tylko dwie permutacje dobre. Dla \(\displaystyle{ n=2}\) takze dwie.

Przyklad:
\(\displaystyle{ n=7, typ \ a \ (4, 3, 5, 2, 6, 1, 7) \mapsto (4, 3, 5, 2, 6, 1) \ n=6 \ typ \ b}\)
\(\displaystyle{ n=7, typ \ b \ (4, 5, 3, 6, 2, 7, 1) \mapsto (3, 4, 2, 5, 1, 6) \ n=6 \ typ \ a}\)

Brak dowodu dla przypadku , gdy m<0