szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Oblicz sumę
PostNapisane: 15 lip 2017, o 13:30 
Użytkownik

Posty: 163
Lokalizacja: Polska
\sum_{k=0}^{n}  {2n+1 \choose 2k+1} 2^{3k} \mod 5

Pomoże ktoś z tym zadaniem?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 16 lip 2017, o 04:59 
Użytkownik
Avatar użytkownika

Posty: 12428
Lokalizacja: czasem Warschau, czasem Breslau
Jakoś nie przychodzi mi do głowy nic lepszego niż znajdowanie jakiejś rekurencji, choć pewnie da się łatwiej. Może aby zmniejszyć liczby (idei to nie zmienia), zauważmy, że 2^{3k}=8^k\equiv 3^k \pmod{5}, więc możemy się równoważnie zając sumą
S_n=\sum_{k=0}^{n} {2n+1 \choose 2k+1} 3^k
Określmy G_n= \sum_{k=0}^{n}{2n+1 \choose 2k}3^k
Skorzystamy wielokrotnie z tożsamości {n\choose r}+{n \choose r+1}={n+1 \choose r+1}
Mamy
S_{n+1}=\sum_{k=0}^{n+1} {2n+3 \choose 2k+1} 3^k=2n+3+3^{n+1}+ \sum_{k=1}^{n}{2n+3 \choose 2k+1}3^k=\\=2n+3+3^{n+1}+ \sum_{k=1}^{n}\left\{ {2n+2\choose 2k+1}+{2n+2 \choose 2k}\right\}3^k=\\=2n+3+3^{n+1}+ \sum_{k=1}^{n}\left\{ {2n+1\choose 2k+1}+{2n+1\choose 2k}+{2n+1 \choose 2k}+{2n+1 \choose 2k-1}\right\}3^k=\\=2n+3+3^{n+1}+ \sum_{k=1}^{n}{2n+1 \choose 2k+1}3^k+3 \sum_{k=1}^{n}{2n+1\choose 2k-1}3^{k-1} +2\sum_{k=1}^{n}{2n+1 \choose 2k}3^k=\\=4S_n+2G_n
Wygląda dość dobrze, sprawdź czy nie ma błędów rachunkowych, bo to zawsze był mój problem.

To teraz spróbujemy zrobić coś podobnego dla ciągu G_n. Mamy:
G_{n+1}=\sum_{k=0}^{n+1}{2n+3 \choose 2k}3^k=1+(2n+3)3^{n+1}+\sum_{k=1}^{n}{2n+3 \choose 2k}3^k=\\=1+ (2n+3)3^{n+1}+\sum_{k=1}^{n}\left\{ {2n+2 \choose 2k}+{2n+2 \choose 2k-1}\right\}3^k=\\=1+ (2n+3)3^{n+1}+ \sum_{k=1}^{n}\left\{{2n+1 \choose 2k}+{2n+1 \choose 2k-1}+{2n+1 \choose 2k-1}+{2n+1 \choose 2k-2} \right\}3^k=\\=1+ (2n+3)3^{n+1}+2 \sum_{k=1}^{n}{2n+1\choose 2k-1}3^k+ \sum_{k=1}^{n}{2n+1\choose 2k}3^k+\sum_{k=1}^{n}{2n+1\choose 2k-2}3^k=\\=6S_n+4G_n

I tak część rzeczy przeliczyłem w pamięci, bo nie chciałoby mi się rozpisywać wszystkiego. Jak czegos nie rozumiesz, to pisz.

Mamy zatem:
\begin{cases} S_{n+1}=4S_n+2G_n \ (*)\\ G_{n+1}=6S_n+4G_n \end{cases}
Gdy pomnożymy to pierwsze równanie stronami przez 2 i odejmiemy stronami od drugiego równania, to otrzymamy:
G_{n+1}-2S_{n+1}=-2S_n\\G_{n+1}=2S_{n+1}-2S_n\\ G_n=2S_n-2S_{n-1}, n \ge 1
Wstawiając tę zależność do (*), otrzymujemy
S_{n+1}=8S_n-4S_{n-1}, n \ge 1

Policzmy teraz ręcznie:
S_0=1, \ S_1=3+3=6\equiv 1\pmod{5}
Teraz więc zaobserwujmy, że ponieważ S_0, S_1 są całkowite, zatem
S_{n+1}=8S_n-4S_{n-1}\equiv 3S_n+S_{n-1} \pmod{5}
Dalej rozpisz to na pałasza dla małych n ze wzoru rekurencyjnego i znajdź jakąś regularność w resztach z dzielenia przez 5 tych wyrazów. Stwierdziłem, że już tak jest prościej niż znaleźć wzór zwarty tej sumy, który nie byłby przyjemny i niewiele byśmy z niego "bezpośrednio" odczytali. Z prostego rozpisania tego wzoru rekurencyjnego można wywnioskować, że
S_n\equiv 3S_{n-2}\pmod{5}, \ n\ge 2
i z tego już łatwo uzyskać jakieś tam sekwencje, czego mi się nie chce robić.
To będzie coś tam takiego:
1,1,3,3,4,4,2,2,1,1\dots
Sam się zżymałem na używanie tych kropek, ale nikt nie powiedział, że nie jestem hipokrytą.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Oblicz sume - zadanie 42  Corey  2
 Oblicz sumę - zadanie 52  xxxxxxx  19
 Oblicz sumę - zadanie 58  Axyomat  2
 Oblicz sume - zadanie 61  Instru  0
 Oblicz sumę - zadanie 63  miki1542  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl