\(\displaystyle{ \sum_{k=0}^{n} {2n+1 \choose 2k+1} 2^{3k} \mod 5}\)
Pomoże ktoś z tym zadaniem?
Oblicz sumę
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Oblicz sumę
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 \(\displaystyle{ 2^{3k}=8^k\equiv 3^k \pmod{5}}\), więc możemy się równoważnie zając sumą
\(\displaystyle{ S_n=\sum_{k=0}^{n} {2n+1 \choose 2k+1} 3^k}\)
Określmy \(\displaystyle{ G_n= \sum_{k=0}^{n}{2n+1 \choose 2k}3^k}\)
Skorzystamy wielokrotnie z tożsamości \(\displaystyle{ {n\choose r}+{n \choose r+1}={n+1 \choose r+1}}\)
Mamy
\(\displaystyle{ 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 \(\displaystyle{ G_n}\). Mamy:
\(\displaystyle{ 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:
\(\displaystyle{ \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 \(\displaystyle{ 2}\) i odejmiemy stronami od drugiego równania, to otrzymamy:
\(\displaystyle{ 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 \(\displaystyle{ (*)}\), otrzymujemy
\(\displaystyle{ S_{n+1}=8S_n-4S_{n-1}, n \ge 1}\)
Policzmy teraz ręcznie:
\(\displaystyle{ S_0=1, \ S_1=3+3=6\equiv 1\pmod{5}}\)
Teraz więc zaobserwujmy, że ponieważ \(\displaystyle{ S_0, S_1}\) są całkowite, zatem
\(\displaystyle{ 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 \(\displaystyle{ n}\) ze wzoru rekurencyjnego i znajdź jakąś regularność w resztach z dzielenia przez \(\displaystyle{ 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
\(\displaystyle{ 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:
\(\displaystyle{ 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ą.
\(\displaystyle{ S_n=\sum_{k=0}^{n} {2n+1 \choose 2k+1} 3^k}\)
Określmy \(\displaystyle{ G_n= \sum_{k=0}^{n}{2n+1 \choose 2k}3^k}\)
Skorzystamy wielokrotnie z tożsamości \(\displaystyle{ {n\choose r}+{n \choose r+1}={n+1 \choose r+1}}\)
Mamy
\(\displaystyle{ 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 \(\displaystyle{ G_n}\). Mamy:
\(\displaystyle{ 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:
\(\displaystyle{ \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 \(\displaystyle{ 2}\) i odejmiemy stronami od drugiego równania, to otrzymamy:
\(\displaystyle{ 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 \(\displaystyle{ (*)}\), otrzymujemy
\(\displaystyle{ S_{n+1}=8S_n-4S_{n-1}, n \ge 1}\)
Policzmy teraz ręcznie:
\(\displaystyle{ S_0=1, \ S_1=3+3=6\equiv 1\pmod{5}}\)
Teraz więc zaobserwujmy, że ponieważ \(\displaystyle{ S_0, S_1}\) są całkowite, zatem
\(\displaystyle{ 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 \(\displaystyle{ n}\) ze wzoru rekurencyjnego i znajdź jakąś regularność w resztach z dzielenia przez \(\displaystyle{ 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
\(\displaystyle{ 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:
\(\displaystyle{ 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ą.