Oblicz sumę:
\(\displaystyle{ \sum_{k=0}^{n} {4n \choose 4k} }\)
Oblicz sumę
- Janusz Tracz
- Użytkownik
- Posty: 4085
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1398 razy
Re: Oblicz sumę
Zauważmy, że
gdzie \(\displaystyle{ \chi_{\left\{ 0,4,8,\dots,4n\right\} } }\) to funkcja charakterystyczna. Wyznacz wykładnicza reprezentację tej funkcji. To znaczy funkcja \(\displaystyle{ \chi_{\left\{ 0,4,8,\dots,4n\right\} } }\) daje się zapisać wzorem postaci \(\displaystyle{ a^k \pm b^k \pm c^k \pm \dots \pm d^k }\) dla pewnych \(\displaystyle{ a,b,c,\dots,d\in\CC}\). Potem powinno być już łatwo.
\(\displaystyle{ \sum_{k=0}^{n} {4n \choose 4k} = \sum_{ 0 \le k \le 4n \\ k \ \equiv \ 0 \text{ mod }4} {4n \choose k} = \sum_{k=0}^{4n} {4n \choose k} \chi_{\left\{ 0,4,8,\dots,4n\right\} } (k), }\)
gdzie \(\displaystyle{ \chi_{\left\{ 0,4,8,\dots,4n\right\} } }\) to funkcja charakterystyczna. Wyznacz wykładnicza reprezentację tej funkcji. To znaczy funkcja \(\displaystyle{ \chi_{\left\{ 0,4,8,\dots,4n\right\} } }\) daje się zapisać wzorem postaci \(\displaystyle{ a^k \pm b^k \pm c^k \pm \dots \pm d^k }\) dla pewnych \(\displaystyle{ a,b,c,\dots,d\in\CC}\). Potem powinno być już łatwo.
-
- Użytkownik
- Posty: 22234
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3759 razy
Re: Oblicz sumę
Dla `i=0,1,2,3` oznaczmy \(\displaystyle{ A_i=\sum_{k=0}^{n-1}\binom{4n}{4k+i}}\)
Mamy
\(\displaystyle{
\begin{align}
2^{4n}=(1+1)^{4n}&=A_0+A_1+A_2+A_3+1\\
0=(1-1)^{4n}&=A_0-A_1+A_2-A_3+1\\
(i+1)^{4n}&=A_0+iA_1-A_2-iA_3+1\\
(-i+1)^{4n}&=A_0-iA_1-A_2+iA_3+1
\end{align}
}\)
Ze wzoru de Moivre'a wyliczamy, że `(1+i)^{4n}=(1-i)^{4n}=2^{2n}\cos n\pi`
Dodając do siebie dwa pierwsze równania, a potem dwa ostatnie dostajemy
\(\displaystyle{
\begin{align}
2^{4n-1}-1&=A_0+A_2\\
2^{2n}\cos n\pi-1&=A_0-A_2,
\end{align}}\)
skąd `A_0=2^{4n-2}+2^{2n-1}\cos n\pi-1`, zaś szukana suma to `A_0+1`
Zainteresowani łatwo wyliczą pozostałe zmienne.
Mamy
\(\displaystyle{
\begin{align}
2^{4n}=(1+1)^{4n}&=A_0+A_1+A_2+A_3+1\\
0=(1-1)^{4n}&=A_0-A_1+A_2-A_3+1\\
(i+1)^{4n}&=A_0+iA_1-A_2-iA_3+1\\
(-i+1)^{4n}&=A_0-iA_1-A_2+iA_3+1
\end{align}
}\)
Ze wzoru de Moivre'a wyliczamy, że `(1+i)^{4n}=(1-i)^{4n}=2^{2n}\cos n\pi`
Dodając do siebie dwa pierwsze równania, a potem dwa ostatnie dostajemy
\(\displaystyle{
\begin{align}
2^{4n-1}-1&=A_0+A_2\\
2^{2n}\cos n\pi-1&=A_0-A_2,
\end{align}}\)
skąd `A_0=2^{4n-2}+2^{2n-1}\cos n\pi-1`, zaś szukana suma to `A_0+1`
Zainteresowani łatwo wyliczą pozostałe zmienne.
-
- Użytkownik
- Posty: 7922
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1672 razy
Re: Oblicz sumę
Twierdzenie
Dla \(\displaystyle{ n\in \NN }\) zachodzi równość:
\(\displaystyle{ \sum_{k=0}^{n} {4n\choose 4k} = \frac{1}{4}\left[ 2^{4n} + (-1)^{n}\cdot 2^{2n+1}\right ] \ \ (^{*}) }\)
Lemat
Dla \(\displaystyle{ k \in \NN }\) prawdziwa jest równość
\(\displaystyle{ \frac{1}{4} \left[(i^{k})^0 + (i^{k})^1 +(i^{k})^2 + (i^{k})^3\right ] = \begin{cases} 1 \ \ jeśli \ \ 4|k \\ 0 \ \ w \ \ pozostałym \ \ przypadku \end{cases} }\)
Z definicji jednostki urojonej \(\displaystyle{ i^2 = -1 }\) oraz podstawienia \(\displaystyle{ a_{k} = {4n\choose k} }\) otrzymujemy
\(\displaystyle{ \sum_{k=1}^{n} {4n\choose 4k} = \sum_{k=1}^{n} \frac{\left( 1 + i^{k} + (-1)^{k} +(-i)^{k}\right)}{4} a_{k} = \sum_{k=0}^{n} \frac{\left( 1 + i^{k} + (-1)^{k} +(-i)^{k}\right)}{4} {4n\choose k} = }\)
\(\displaystyle{ =\frac{1}{4}\sum_{k=1}^{n}{4n\choose k} + \frac{1}{4}\sum_{k=)0}^{n} i^{k}{4n\choose k} + \frac{1}{4} \sum_{k=1}^{n}(-1)^{k}{4n\choose k} + \frac{1}{4}\sum_{k=1}^{n} i^{k} {4n\choose k} = \frac{( 1+1)^{4n} + (1+i)^{4n} + (1-1)^{4n} + (1-i)^{4n}}{4}= }\)
\(\displaystyle{ = \frac{2^{4n}}{4} + \frac{(-4)^{n}}{4} + \frac{0}{4} + \frac{(-4)^{n}}{4} = \frac{2^{4n}}{2^2} + \frac{(-1)^{n} \cdot 2^{2n}}{2^2} + 0 + \frac{(-1)^{n}\cdot 2^{2n}}{2^2} = 2^{4n-2} +(-1)^{n} \cdot 2^{2n-2} +(-1)^{n} \cdot 2^{2n-2} = }\)
\(\displaystyle{ = 2^{4n-2} + (-1)^{n} \cdot 2\cdot 2^{2n-2} = 2^{4n-2} +(-1)^{n} \cdot 2^{2n-1} = 2^{-2}\cdot 2^{4n} + (-1)^{n}\cdot 2^{-2}\cdot 2^{2n+1} = \frac{1}{4}\left( 2^{4n}+ 2^{2n+1}\right)}\)
\(\displaystyle{ \Box }\)
\(\displaystyle{ (^{*}) }\) H. W. Gould. Combinatorial Identities. Copyright @ Henry W. Gould 1972 Printed by Morganmtown Printing and Binding Co.
Dla \(\displaystyle{ n\in \NN }\) zachodzi równość:
\(\displaystyle{ \sum_{k=0}^{n} {4n\choose 4k} = \frac{1}{4}\left[ 2^{4n} + (-1)^{n}\cdot 2^{2n+1}\right ] \ \ (^{*}) }\)
Lemat
Dla \(\displaystyle{ k \in \NN }\) prawdziwa jest równość
\(\displaystyle{ \frac{1}{4} \left[(i^{k})^0 + (i^{k})^1 +(i^{k})^2 + (i^{k})^3\right ] = \begin{cases} 1 \ \ jeśli \ \ 4|k \\ 0 \ \ w \ \ pozostałym \ \ przypadku \end{cases} }\)
Z definicji jednostki urojonej \(\displaystyle{ i^2 = -1 }\) oraz podstawienia \(\displaystyle{ a_{k} = {4n\choose k} }\) otrzymujemy
\(\displaystyle{ \sum_{k=1}^{n} {4n\choose 4k} = \sum_{k=1}^{n} \frac{\left( 1 + i^{k} + (-1)^{k} +(-i)^{k}\right)}{4} a_{k} = \sum_{k=0}^{n} \frac{\left( 1 + i^{k} + (-1)^{k} +(-i)^{k}\right)}{4} {4n\choose k} = }\)
\(\displaystyle{ =\frac{1}{4}\sum_{k=1}^{n}{4n\choose k} + \frac{1}{4}\sum_{k=)0}^{n} i^{k}{4n\choose k} + \frac{1}{4} \sum_{k=1}^{n}(-1)^{k}{4n\choose k} + \frac{1}{4}\sum_{k=1}^{n} i^{k} {4n\choose k} = \frac{( 1+1)^{4n} + (1+i)^{4n} + (1-1)^{4n} + (1-i)^{4n}}{4}= }\)
\(\displaystyle{ = \frac{2^{4n}}{4} + \frac{(-4)^{n}}{4} + \frac{0}{4} + \frac{(-4)^{n}}{4} = \frac{2^{4n}}{2^2} + \frac{(-1)^{n} \cdot 2^{2n}}{2^2} + 0 + \frac{(-1)^{n}\cdot 2^{2n}}{2^2} = 2^{4n-2} +(-1)^{n} \cdot 2^{2n-2} +(-1)^{n} \cdot 2^{2n-2} = }\)
\(\displaystyle{ = 2^{4n-2} + (-1)^{n} \cdot 2\cdot 2^{2n-2} = 2^{4n-2} +(-1)^{n} \cdot 2^{2n-1} = 2^{-2}\cdot 2^{4n} + (-1)^{n}\cdot 2^{-2}\cdot 2^{2n+1} = \frac{1}{4}\left( 2^{4n}+ 2^{2n+1}\right)}\)
\(\displaystyle{ \Box }\)
\(\displaystyle{ (^{*}) }\) H. W. Gould. Combinatorial Identities. Copyright @ Henry W. Gould 1972 Printed by Morganmtown Printing and Binding Co.