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

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

Pomoże ktoś z tym zadaniem?
Góra
Mężczyzna Online
PostNapisane: 16 lip 2017, o 03:59 
Użytkownik
Avatar użytkownika

Posty: 13160
Lokalizacja: Wrocław
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