###### tags: `Matematyka Dyskretna M`

# Lista 7

## 1

n pionków możemy ułożyć na 1 sposób.

n-1 pionków możemy ułożyć na $\binom{n}{1}\binom{n}{1}$, ponieważ musimy wybrać, w której kolumnie i w którym wierszu nie wstawimy tego pionka, a możemy jedną kolumnę wybrać na $\binom{n}{1}$ sposobów oraz jeden wiersz na $\binom{n}{1}$ sposobów.

n-2 pionków możemy ułożyć na $\binom{n}{2}\binom{n}{2}$, ponieważ musimy wybrać, w których kolumnach i w których wierszach nie wstawimy pionków, a możemy dwie kolumny wybrać na $\binom{n}{2}$ sposobów oraz dwa wiersze na $\binom{n}{2}$ sposobów.
itd..

Co daje nam:

$\displaystyle\sum_{i=0}^{n}\binom{n}{i}^2 = \binom{2n}{n}$

## 2
$F_{n+1}=\displaystyle\sum_{i=0}^n\binom{n-i}{i}$
Dowód przeprowadzę przez indukcję po $n$.
**1$^\circ$**
Dla n=0
$L=F_1=1$
$P=\binom{0}{0}=1$

Dla n=1
$L=F_2=1$
$P=\binom{1}{0}+\binom{0}{1}=1$
**2$^\circ$**
Załóżmy, że dla $\forall_{k<n+1}$ podana równość zachodzi. Wtedy dla $n+1$
$F_{n+1}=F_{n}+F_{n-1}=\displaystyle\sum_{i=0}^{n-1}\binom{n-i-1}{i} +\displaystyle\sum_{i=0}^{n-2}\binom{n-i-2}{i}=$
$=\binom{n-1}{0}+\displaystyle\sum_{i=1}^{n-1}\binom{n-i-1}{i} +\displaystyle\sum_{i=1}^{n-1}\binom{n-i-1}{i-1}=\binom{n-1}{0}+\displaystyle\sum_{i=1}^{n-1}\binom{n-i-1}{i}+\binom{n-i-1}{i-1}=$
$=\binom{n}{0}+\displaystyle\sum_{i=1}^{n-1}\binom{n-i}{i}=\displaystyle\sum_{i=0}^{n-1}\binom{n-i}{i}=\displaystyle\sum_{i=0}^n\binom{n-i}{i}$

Co kończy dowód indukcyjny.

$F_{m+2n}=\displaystyle\sum_{i=0}^n\binom{n}{i}F_{i+m}$
Dowód przeprowadzę przez indukcję po $n$.

**1$^\circ$**
Dla n=0
$L=F_m$
$P=\binom{0}{0}F_{0+m}=F_m=L$

Dla n=1
$L=F_{m+2}$
$P=\binom{1}{0}F_m+\binom{1}{1}F_{m+1}=F_m+F_{m+1}=F_{m+2} = L$
**2$^\circ$**
Załóżmy, że dla $\forall_{k<n}$ podana równość zachodzi. Wtedy dla $n$

$P=\displaystyle\sum_{i=0}^n\binom{n}{i}F_{i+m}=\displaystyle\sum_{i=0}^n\binom{n-1}{i}F_{i+m}+\binom{n-1}{i-1}F_{i+m}=$

$=\displaystyle\sum_{i=0}^n\binom{n-1}{i}F_{i+m}+\displaystyle\sum_{i=0}^n\binom{n-1}{i-1}F_{i+m}=$

$=\binom{n-1}{n} + \displaystyle\sum_{i=0}^{n-1}\binom{n-1}{i}F_{i+m}+\displaystyle\sum_{i=1}^{n}\binom{n-1}{i-1}F_{i+m}=$

$=\binom{n-1}{n} + \displaystyle\sum_{i=0}^{n-1}\binom{n-1}{i}F_{i+m}+\displaystyle\sum_{i=0}^{n-1}\binom{n-1}{i}F_{i+m+1}=$
$=F_{m+2n-2}+F_{m+2n-2+1}=F_{m+2n-2}+F_{m+2n-1}=F_{m+2n}$

Co kończy dowód indukcyjny.

## 3

$|\Omega|=\frac{(2n)!}{2^n}$ mamy $2n$ liczb, z czego nie rozróżniamy takich samych cyfr.

$|A_i|$ moc takiego zbioru, że i-ta para liczb sąsiaduje ze sobą.
$|A_i|=\frac{(2n-1)!}{2^{n-1}}$ (Traktujemy tę parę jako "jedną jednostkę").

$|A_1\cap A_2\cap ... \cap A_k|=\frac{(2n-k)!}{2^{n-k}}$

Z zasady włączeń i wyłączeń:

$|\Omega|-|A_1\cup A_2\cup...\cup A_n|=\frac{(2n)!}{2^n}-\displaystyle\sum_{i=1}^n(-1)^{i+1}\binom{n}{i}\frac{(2n-i)!}{2^{n-i}}=\displaystyle\sum_{i=0}^n(-1)^i\binom{n}{i}\frac{(2n-i)!}{2^{n-i}}$

## 4

$a_0=1$
$a_1=0$
$a_n=\frac{a_{n-1}+a_{n-2}}{2}$

$a_n-\frac{a_{n-1}}{2}-\frac{a_{n-2}}{2}=0$
$<a_n-\frac{a_{n-1}}{2}-\frac{a_{n-2}}{2}>=<0>$
$(E^2-\frac{E}{2}-\frac{1}{2})<a_n> = <0>$
$(E-1)(E+\frac{1}{2})<a_n> = <0>$

Czyli $a_n=\alpha\times1^n+\beta\times(-\frac{1}{2})^n$
$a_0=\alpha+\beta = 1$
$a_1=\alpha-\frac{1}{2}\beta=0$

Rozwiązując układ równań otrzymujemy

$\beta=\frac{2}{3}$
$\alpha=\frac{1}{3}$
Czyli $a_n=\frac{1}{3}+\frac{2}{3}\times(-\frac{1}{2})^n$

## 5
### a
$a_{n+2}=2a_{n+1}-a_n+3^n-1$ dla $a_0=a_1=0$
$a_{n+2}-2a_{n+1}+a_n=3^n-1$
$(E^2-2E+1)<a_n>=<3^n-1>$
$(E^2-2E+1)<a_n>=<3^n-1>$
$(E-1)^2(E-3)<a_n>=<3^{n+1}-1-3^{n+1}+3>$
$(E-1)^2(E-3)<a_n>=<2>$
$(E-1)^3(E-3)<a_n>=<0>$

$a_n=\alpha\times1^n+\beta\times n\times1^n+\gamma\times n^21^n+\delta\times3^n$
$a_0=0=\alpha+\delta$
$a_1=0=\alpha+\beta+\gamma+3\delta$
$a_2=0=\alpha+2\beta+4\gamma+9\delta$
$a_3=2=\alpha+3\beta+9\gamma+27\delta$

Rozwiązując układ równań otrzymujemy

$\alpha=-\frac{1}{4}$
$\beta=0$
$\gamma=-\frac{1}{2}$
$\delta=\frac{1}{4}$

Czyli:
$a_n=-\frac{1}{4}-\frac{n^2}{2}+\frac{3^n}{4}$

### b

$a_{n+2}= 4a_{n+1}−4a_n+n2^{n+1}$ dla $a_0=a_1= 1$
$a_{n+2}-4a_{n+1}+4a_n=n2^{n+1}$
$<a_{n+2}-4a_{n+1}+4a_n>=<n2^{n+1}>$
$(E^2-4E+4)<a_n>=<n2^{n+1}>$
$(E-2)^2<a_n>=<n2^{n+1}>$
$(E-2)^4<a_n>=<0>$

$a_n=\alpha\times2^n+\beta\times n\times2^n+\gamma\times n^2\times2^n+\delta\times n^3\times2^n$

### c
$a_{n+2}= 2^{n+1}−a_{n+1}−a_n$ dla $a_0=a_1= 1$
$a_{n+2}+a_{n+1}+a_n=2^{n+1}$
$<a_{n+2}+a_{n+1}+a_n>=<2^{n+1}>$
$(E^2+E+1)<a_n>=<2^{n+1}>$
$(E^2+E+1)(E-2)<a_n>=<0>$
$(E-\frac{-1-\sqrt{3}i}{2})(E-\frac{-1+\sqrt{3}i}{2})(E-2)<a_n>=<0>$

$a_n=\alpha\times(\frac{-1-\sqrt{3}i}{2})^n+ \beta\times(\frac{-1+\sqrt{3}i}{2})^n + \gamma\times2^n$

## 8
$s_{n+1}=s_n+(n+1)2^{n+1}$
$<s_{n+1}-s_n>=<(n+1)2^{n+1}>$
$(E-1)<s_n>=<(n+1)2^{n+1}>$
$(E-1)(E-2)<s_n>=(E-2)<(n+1)2^{n+1}>$
$(E-1)(E-2)<s_n>=<2^{n+2}>$
$(E-1)(E-2)^2<s_n>=(E-2)<2^{n+2}>$
$(E-1)(E-2)^2<s_n>=<0>$

Czyli:
$s_n=\alpha\times1^n + \beta\times2^n + \gamma\times n2^n$

$s_1=2=\alpha+2\beta+2\gamma$
$s_2=10=\alpha+4\beta+8\gamma$
$s_3=34=\alpha+8\beta+24\gamma$

Rozwiązując układ równań otrzymujemy:
$\alpha=2$
$\beta=-2$
$\gamma=2$

Czyli $s_n=2-2^{n+1}+n2^{n+1}=2-2^{n+1}(1-n)=2+(n-1)2^{n+1}$

## 9

Weźmy ciąg $a_n$, gdzie $a_n$ jest równy liczbie tych ciągów o długości n.

Wtedy $a_n = b_n + c_n + d_n$, gdzie $b_n, c_n, d_n$ to są odpowiednio ciągi zakończone liczbą 0,1,2.

Wiemy, że $b_n=b_{n-1}+c_{n-1}+d_{n-1}$
$c_n=b_{n-1}+d_{n-1}$ (bo nie mogą się poprzednie ciągi kończyć liczbą 1)
$d_n=b_{n-1}+c_{n-1}$ (analogicznie jak wyżej tylko dla liczby 2)

Czyli
$a_n=b_n + c_n + d_n=b_{n-1}+c_{n-1}+d_{n-1}+b_{n-1}+d_{n-1}+b_{n-1}+c_{n-1}=$
$=3b_{n-1}+2c_{n-1}+2d_{n-1}=2a_{n-1}+b_{n-1}=2a_{n-1}+b_{n-2}+c_{n-2}+d_{n-2}=$
$=2a_{n-1}+a_{n-2}$

$a_{n+2}=2a_{n+1}+a_n$
$a_{n+2}-2a_{n+1}-a_n=0$
$<a_{n+2}-2a_{n+1}-a_n>=<0>$
$(E^2-2E-1)<a_n>=<0>$
$(E-1-\sqrt{2})(E-1+\sqrt{2})<a_n>=<0>$

$a_n=\alpha\times (1+\sqrt{2})^n+\beta\times(1-\sqrt{2})^n$

$a_0=1=\alpha+\beta$
$a_1=3=\alpha(1 +\sqrt{2})+\beta(1 - \sqrt{2})$

Rozwiązując układ równań otrzymujemy:

$\alpha=\frac{1 + \sqrt{2}}{2}$
$\beta=\frac{1 - \sqrt{2}}{2}$

Czyli:

$a_n=\frac{1 + \sqrt{2}}{2}\times (1+\sqrt{2})^n + \frac{1 - \sqrt{2}}{2}\times(1-\sqrt{2})^n$