Liczba elementów jako krotność

[Harry Xin]

Wyprowadź wzór na liczbę takich podzbiorów zbioru n-elementowego, których liczba elementów jest krotnością czwórki.

Ukryta treść:    

Odpowiedź: \(\displaystyle{ \left(\sqrt{2}\right)^{n}\cos \frac{n\pi}{4}}\)

[abc666]

Tak jak przy "ciekawej sumie" w innym temacie 116346.htm będzie to wyglądało, tylko trzeba ciąg \(\displaystyle{ 1,0,0,0,1,0...}\) znaleźć

[Wasilewski]

A ta odpowiedź raczej poprawna nie jest; radzę się nią nie sugerować.

[abc666]

Czy chodzi o to że w wyprowadzaniu trzeba wykorzystać coś konkretnego?
Mamy obliczyć
\(\displaystyle{ {n \choose 0}+ {n \choose 4} + {n \choose 8} +...=}\)
Więc wykorzystujemy taki ciąg
\(\displaystyle{ \frac{1}{4} \left(2\cos \left( \frac{n\pi}{2} \right)+1+(-1)^n \right)= \frac{1}{4} \left(e^{ i\frac{n\pi}{2} }+e^{ -i\frac{n\pi}{2} }+1+(-1)^n \right)}\)
i dalej postępujemy tak jak w podanym wyżej temacie.
Źle myślę?

[Harry Xin]

Ma wyjść coś podobnego do odpowiedzi. Mówię podobnego, skoro jest błędna...

[xiikzodz]

Zapiszę to w możliwie dużej ogólności, żeby był algorytm do podobnych sytuacji.

W przypadku ciągu okresowego o okresie \(\displaystyle{ n}\) użyjemy liczby \(\displaystyle{ \varepsilon_n=e^{\frac{2\pi i}n}=\exp\left(\frac{2\pi i}{n}\right)}\).

Tu wystarczy \(\displaystyle{ i}\).

Każdy ciąg okresowy o długosci okresu \(\displaystyle{ b}\) należy do \(\displaystyle{ n}\)-wymiarowej przestrzeni liniowej rozpiętej na ciągach, których elementy dane są wzorami:

\(\displaystyle{ \sum_{k=0}^{n-1}a_k \exp\left(\frac{2km\pi i}{n}\right)}\).

Mając \(\displaystyle{ n}\) pierwszych wyrazów takiego ciągu okresowego \(\displaystyle{ x_0,...,x_{n-1}}\) współczynniki \(\displaystyle{ a_n}\) wyznaczamy z układu równań:

\(\displaystyle{ x_m=\sum_{k=0}^{n-1}a_k \exp\left(\frac{2km\pi i}{n}\right)}\)

\(\displaystyle{ m=0,1,...,n-1}\).

Tutaj mamy:

\(\displaystyle{ \exp\left(\frac{2\pi i}{4}\right)=i}\)

oraz

\(\displaystyle{ x_0=1}\)

\(\displaystyle{ x_1=x_2=x_3=0}\).

Wystarczy więc rozwiązać układ równań:

\(\displaystyle{ \left\{\begin{array}{ccccccccc}
a_0&+&a_1&+&a_2&+&a_3&=&1\\
a_0&+&ia_1&-&a_2&-&ia_3&=&0\\
a_0&-&a_1&+&a_2&-&a_3&=&0\\
a_0&-&ia_1&-&a_2&+&ia_3&=&0\\
\end{array}\right.}\)

czyli odwrócić macierz:

\(\displaystyle{ M=\begin{pmatrix}
1&1&1&1\\
1&i&-1&-i\\
1&-1&1&-1\\
1&-i&-1&i
\end{pmatrix}}\)

i odwrotnością podziałać na wektor \(\displaystyle{ \begin{pmatrix}1\\0\\0\\0\end{pmatrix}}\).

\(\displaystyle{ M}\) jest ortogonalna, symetryczna i ma kolumny o tej samym kwadracie normy równym \(\displaystyle{ 4}\), więc jej odwrotność to:

\(\displaystyle{ M^{-1}=\frac 14 M^T=\frac 14 M=\frac 14\begin{pmatrix}
1&1&1&1\\
1&i&-1&-i\\
1&-1&1&-1\\
1&-i&-1&i
\end{pmatrix}}\)

Skąd

\(\displaystyle{ M^{-1}\begin{pmatrix}1\\0\\0\\0\end{pmatrix}=\frac 14 \begin{pmatrix}1\\1\\1\\1\end{pmatrix}}\)

Zatem szukanym ciągiem jest:

\(\displaystyle{ x_n=\frac 14(1^n+i^n+(-1)^n+(-i)^n)}\)

Wracając do zadania. Rozważamy więc:

\(\displaystyle{ \frac 14((1+1)^n+(1+i)^n+(1-1)^n+(1-i)^n)=\frac 14(2^n+(1+i)^n+(1-i)^n)=}\)

\(\displaystyle{ =\frac 14(2^n+(\sqrt 2)^n(\varepsilon_8^n+\overline{\varepsilon_8}^n))=\frac 14\left(2^n+(\sqrt 2)^n\cos\frac{n\pi}{4}\right)}\).

Tak mi wyszło, ale mogą być błędy.

[Wasilewski]

Zgubiła Ci się dwójka, powinno być tak:
\(\displaystyle{ \frac{1}{4}\left( 2^{n} + 2 (\sqrt{2})^{n} cos \frac{n \pi}{4}\right)}\)