# Lista 2

Zadeklarowane zadania:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|:------------:|:---:| --- | ------------ | ------------ | ------------ | --- | ------------ | ------------ | --- | --- | --- | --- | --- | ------------ |
| $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | | $\checkmark$ | $\checkmark$ | $\checkmark$ | | | | $\checkmark$ | $\checkmark$ |

## Zadanie 1
Wykazać $\lfloor a n\rfloor + \lfloor (1-a)n \rfloor = n-1$, gdzie $a \in \Bbb{IQ}$ oraz $n \in \Bbb{N}$.

$$\lfloor a n\rfloor + \lfloor n - an \rfloor = \lfloor a n\rfloor + \lfloor n + (- an) \rfloor \stackrel{1}{=} \lfloor a n\rfloor + n + \lfloor - an \rfloor =$$

$$ \lfloor a n\rfloor + n - \lceil an \rceil \stackrel{2}{=} n-1$$

1. $n \in \Bbb{N}$, stąd $\lfloor n + (- an) \rfloor = n + \lfloor- an \rfloor$
2. $an \in \Bbb{IQ}$, zatem $\lfloor a n\rfloor - \lceil an \rceil = -1$

Analogiczna równość dla powały:

$$\lceil a n\rceil + \lceil (1-a)n \rceil = n+1$$

Dowód:

$$\lceil a n\rceil + \lceil (1-a)n \rceil = \lceil a n\rceil + n + \lceil -an \rceil = \lceil a n\rceil + n - \lfloor an \rfloor = n+1$$

## Zadanie 2

Obliczyć:
$$\Big\lfloor \frac{x}{m} \Big\rfloor + \Big\lfloor \frac{x+1}{m} \Big\rfloor + \Big\lfloor \frac{x+2}{m} \Big\rfloor + ... + \Big\lfloor \frac{x + m - 1}{m} \Big\rfloor$$

gdzie $x \in \Bbb{R}$ oraz $m \in \Bbb{N}$.

Niech $x = dm + r$, gdzie $d \in \Bbb{N}, r \in [0, m)$.

Mamy wtedy:
$$\sum^{m-1}_{i=0}a_i = \sum^{m-1}_{i=0}\Bigl\lfloor \frac{x + i}{m} \Bigr\rfloor = \sum^{m-1}_{i=0}\Bigl\lfloor \frac{dm + r + i}{m} \Bigr\rfloor = \sum^{m-1}_{i=0}\Big(d + \Bigl\lfloor \frac{r + i}{m} \Bigr\rfloor\Big)$$

Wiemy, że $r+i \in [0, 2m -1)$, zatem $\lfloor \frac{r + i}{m} \rfloor \in \{0,1\}$

$$a_i = \begin{cases} d, & r + i < m\\ d+1, & r + i \geq m \end{cases}$$

$$\sum^{m-1}_{i=0}a_i = dm + \sum^{m-1}_{\lceil m - r \rceil}1 = dm + \sum^{m-1}_{m - \lfloor r \rfloor}1 = dm + \lfloor r \rfloor = \lfloor x \rfloor$$

## Zadanie 3

a) $a_n = na_{n-2}$
Chcąc policzyć $a_0 \space i \space a_1$ z zależności rekurencyjnej musielibyśmy odwoływać się do nieistniejących wyrazów ciągu. Dla policzenia $a_2$ wystarczy $a_0$, a dla $a_3$ potrzeba $a_1$.
Potrzebne są zatem tylko **2** warunki początkowe.

b) $a_n = a_{n-1} + a_{n-3}$

Chcąc policzyć $a_0, \space a_1, \space a_2$ z zależności rekurencyjnej musielibyśmy odwoływać się do nieistniejących wyrazów ciągu. Dla $a_3$ wystarczą nam $a_0, \space a_2$, a dla $a_4$ -- $a_2, a_3$.
Stąd potrzebujemy **3** warunki początkowe.

c) $a_n = 2a_{\lfloor \frac{a}{2} \rfloor}+n$
Chcąc policzyć $a_0$ mamy $a_0 = 2a_0 + 0$, czyli $a_0 = 0$.
Potrzebujemy zatem **0** warunków początkowych.

## Zadanie 4
Policzyć zależności rekurencyjne:

#### a) $fn = f{n-1} + 3^n$ dla $n > 1 \space i \space f_1 = 3$

$$f_n = f_{n-1} + 3^n =f_{n-2} + 3^{n-1} + 3^n = f_{n-2} + 3^{n-2}+ 3^{n-1} + 3^n =$$

$$3 + 3^2 + ... + 3^{n-2}+ 3^{n-1} + 3^n = \sum_{i=1}^{n} 3^i$$

#### b) $h_n = h_{n-1} + (-1)^{n+1}n$ dla $n > 1 \space i \space h_1 = 1$

$$h_n = h_{n-1} + (-1)^{n+1}n =h_{n-2} + (-1)^n(n-1) + (-1)^{n+1}n =$$

$$h_{n-3} + (-1)^{n-1}(n-2) + (-1)^n(n-1) + (-1)^{n+1}n =$$

$$(-1)^21 + (-1)^32+...+(-1)^{n-1}(n-2) + (-1)^n(n-1) + (-1)^{n+1}n = $$

$$\sum^n_{i=1}(-1)^{i+1}i$$

#### c) $l_n = l_{n-1}l_{n-2}$ dla $n > 2 \space i \space l_1=l_2=2$

$$l_n = l_{n-1}l_{n-2} = l_{n-2}l_{n-3}l_{n-2} = (l_{n-2})^2l_{n-3} = (l_{n-3}l_{n-4})^2l_{n-3} =$$

$$(l_{n-3})^3(l_{n-4})^2 = (l_{n-4})^5(l_{n-5})^3 = (l_{n-5})^8(l_{n-6})^5 = ... =$$

$$(l_{n-(n-1)})^{F_{n-2}}(l_{n-(n-2)})^{F_{n-1}} = 2^{F_{n-2}}2^{F_{n-1}} = 2^{F_n}$$

## Zadanie 5

#### a) $\begin{cases} a_0 = 1 \\a_n = \frac{2}{a_{n-1}}\end{cases}$

Niech % oznacza działanie modulo.
$$a_n = 2^{n\%2}$$

Dowód:
$1^{\circ}$ $n=0$

$$a_0 = 1 = 2^{0\%2}$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N} \space$ zachodzi $a_k = 2^{k\%2}$.

$$a_{n} \stackrel{zal. rek.}{=} \frac{2}{a_{n-1}} \stackrel{zał. ind.}{=} \frac{2}{2^{(n-1)\%2}} = 2^{1-(n-1)\%2}$$

$2.1$ Jeśli n-1 jest nieparzyste $\space 2^{1-(n-1)\%2} = 2^{1-1} = 2^0 = 2^{n\%2}$.

$2.2$ Jeśli n-1 jest parzyste $\space 2^{1-(n-1)\%2} = 2^{1-0} = 2^1 = 2^{n\%2}$.

#### b) $\begin{cases} b_0 = 0 \\b_n = \frac{1}{1 + b_{n-1}}\end{cases}$

$$b_n = \frac{F_n}{F_{n+1}}$$

Dowód:
$1^{\circ}$ $n=0$
$$b_0 = 0 = \frac{F_0}{F_1}$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N} \space$ zachodzi $b_k = \frac{F_k}{F_{k+1}}$.

$$b_n = \frac{1}{1 + b_{n-1}} \stackrel{zał. ind.}{=}
\frac{1}{1 + \frac{F_{n-1}}{F_n}}=
\frac{F_n}{F_n + F_{n-1}} = \frac{F_n}{F_{n+1}}$$

c) $\begin{cases} c_0 = 1 \\c_n = \sum_{i=0}^{n-1}c_i\end{cases}$

$$\begin{cases} c_0 = 1 \\ c_n = 2^{n-1} \space dla \space n \geq 1\end{cases}$$

Dowód:
$1^{\circ}$ $n=1$
$$c_1 = c_0 = 1 = 2^{1-1}$$

$2^{\circ}$ Załóżmy, że dla każdego $1 \leq k < n, k \in \Bbb{N} \space$ zachodzi $c_k = 2^{k-1}$.

$$c_n = \sum_{i=0}^{n-1}c_i =
c_{n-1} + \sum_{i=0}^{n-2}2^{i-1} \stackrel{zal.rek.}{=}
c_{n-1} + c_{n-1} \stackrel{zał.ind.}{=} 2 \cdot 2^{n-2} = 2^{n-1}$$

d) $\begin{cases} d_0 = 1 \\ d_1 = 2 \\
d_n = \frac{d_{n-1}^2}{d_{n-2}}\end{cases}$

$$d_n = 2^n$$

Dowód:
$1^{\circ}$ $n= \in \{0,1\}$
$$d_0 = 1 = 2^0$$

$$d_1 = 2 = 2^1$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N} \space$ zachodzi $d_k = 2^k$.

$$d_n = \frac{d_{n-1}^2}{d_{n-2}} \stackrel{zał.ind.}{=}
\frac{(2^{n-1})^2}{2^{n-2}} = 2^{2n-2-n+2} = 2^n$$

## Zadanie 6

a) $\begin{cases}
y_0=y_1=1 \\
y_n = \frac{y_{n-1}^2+y_{n-2}}{y_{n-1} + y_{n-2}}
\end{cases}$

$$y_n = 1$$

Dowód:
$1^{\circ}$ $n= \in \{0,1\}$
$$y_0=y_1=1$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N} \space$ zachodzi $y_k = 1$.

$$y_n = \frac{y_{n-1}^2+y_{n-2}}{y_{n-1} + y_{n-2}} \stackrel{zał.ind.}{=} \frac{1^2 + 1}{1+ 1} = 1$$

b) $\begin{cases}
z_0 = 1 \\
z_1 = 2 \\
z_n = \frac{z_{n-1}^2-1}{z_{n-2}}
\end{cases}$

$$z_n = n+1$$

Dowód:
$1^{\circ}$ $n= \in \{0,1\}$
$$z_0 = 0 + 1$$

$$z_1 = 1 + 1$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N} \space$ zachodzi $z_k = k + 1$.

$$z_n = \frac{z_{n-1}^2-1}{z_{n-2}} \stackrel{zał.ind.}{=}
\frac{n^2 -1 }{n - 1} =
\frac{(n -1)(n+1) }{n - 1} = n + 1$$

c)$\begin{cases}
t_0 = 0 \\
t_1 = 1 \\
t_n = \frac{(t_{n-1} - t_{n-2} + 3)^2}{4}
\end{cases}$

$$t_n = n^2$$

Dowód:
$1^{\circ}$ $n= \in \{0,1\}$
$$t_0 = 0^2$$

$$t_1 = 1^2$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N} \space$ zachodzi $t_k = k^2$.

$$t_n \stackrel{zal.rek.}{=}
\frac{(t_{n-1} - t_{n-2} + 3)^2}{4} \stackrel{zał.ind.}{=}
\frac{((n-1)^2 - (n-2)^2 + 3)^2}{4} =$$

$$
\frac{(n^2 -2n + 1 - n^2 + 4n - 4 + 3)^2}{4} =
\frac{(2n)^2}{4} = n^2
$$

## Zadanie 8
Rozwiązać zależność rekurencyjną:

$\begin{cases} a_n = \frac{1 + a_{n-1}}{a_{n-2}} \\ a_0 = \alpha \\ a_1 = \beta \end{cases}$

Policzmy kilka początkowych wyrazów ciągu:

$\begin{cases} a_0 = \alpha \\
a_1 = \beta \\
a_2 = \frac{1 + \beta}{\alpha} \\
a_3 = \frac{1 + \frac{1 + \beta}{\alpha}}{\beta} = \frac{\alpha + 1 + \beta}{\alpha \beta}\\
a_4 = \frac{1 + \frac{\alpha + 1 + \beta}{\alpha \beta}}{\frac{1 + \beta}{\alpha}} = \frac{\alpha\beta + \alpha + \beta + 1}{(1+\beta)\beta} = \frac{\alpha(\beta + 1) + (\beta + 1)}{(1+\beta)\beta} = \frac{\alpha + 1}{\beta} \\
a_5 = \frac{1 + \frac{\alpha + 1}{\beta}}{\frac{\alpha + 1 + \beta}{\alpha \beta}} = \frac{\alpha + \beta + 1}{\frac{\alpha + \beta + 1}{\alpha}} = \alpha \\
a_6 = \frac{1 + \alpha}{\frac{\alpha + 1}{\beta}} = \beta\end{cases}$

Zauważmy, że wartości odpowiednich wyrazów ciągu będą się powtarzać. Zależność rekurencyjna wymaga 2 ostatnich elementów ciągu, ponieważ $a_0, a_1$ odpowiadają $a_5, a_6$, stąd $a_7$ wyliczymy do tej samej wartości co $a_2$ i dalej analogicznie.

Otrzymujemy zatem wzór:
(Niech % oznacza działanie modulo).

$a_n = \begin{cases} \alpha, & n\%5=0 \\
\beta & n\%5=1 \\
\frac{1 + \beta}{\alpha}, & n\%5=2 \\
\frac{\alpha + 1 + \beta}{\alpha \beta}, & n\%5=3 \\
\frac{\alpha + 1}{\beta}, & n\%5=4 \end{cases}$

Aby ciąg $a_n$ był określony dla wszystkich n, żaden jego wyraz nie może być równy 0, zatem:

- $\alpha \neq 0$
- $\beta \neq 0$
- $\frac{1 + \beta}{\alpha} \neq 0 \implies \beta \neq -1$
- $\frac{\alpha + 1}{\beta} \neq 0 \implies \alpha \neq -1$
- $\frac{\alpha + 1 + \beta}{\alpha \beta} \neq 0 \implies \alpha + \beta \neq -1$

## Zadanie 9
Rozwiązać zależności rekurencyjne:

a) $\begin{cases} f(1) = 1 \\
f(n) = f(\lfloor\frac{n}{2}\rfloor) + f(\lceil\frac{n}{2}\rceil) + 1\end{cases}$

Teza: $f(n) = 2n-1$ dla $n \in \Bbb{N}, n \geq 1$

Dowód indukcyjny:
$1^{\circ}$ $n \in \{1,2\}$
$$f(1) = 1 = 2\cdot1 - 1$$

$$f(2) \stackrel{zal. rek.}{=} f(\lfloor \frac{2}{2}\rfloor) + f(\lceil \frac{2}{2}\rceil) + 1 = 1 + 1 + 1 = 2 \cdot2 - 1$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N}$ zachodzi $f(k) = 2k - 1$. Pokażmy, że zachodzi $f(n) = 2n - 1$.

- Dla n parzystego mamy:

$$f(n) \stackrel{zal.rek.}{=} f(\lfloor\frac{n}{2}\rfloor) + f(\lceil\frac{n}{2}\rceil) + 1 \stackrel{n \space parzyste}{=} f(\frac{n}{2}) + f(\frac{n}{2}) + 1 \stackrel{zał.ind. }{=}$$

$$n - 1 + n -1 + 1 = 2n -1$$

- Dla n nieparzystego mamy:
$$f(n) \stackrel{zal.rek.}{=} f(\lfloor\frac{n}{2}\rfloor) + f(\lceil\frac{n}{2}\rceil) + 1 \stackrel{n \space nieparzyste}{=} f(\frac{n-1}{2}) + f(\frac{n+1}{2}) + 1 \stackrel{zał.ind. }{=}$$

$$(n-1 - 1) + (n + 1 - 1) + 1 = 2n -1$$

Co należało pokazać.

b) $\begin{cases} g(0) = 0\\
g(n) = g(\lfloor \frac{n}{2} \rfloor) + \lfloor log_2n \rfloor\end{cases}$

Teza: $g(n) = \sum_{k=0}^{\lfloor log_2n \rfloor} k = \frac{(1+\lfloor log_2n \rfloor)\lfloor log_2n \rfloor}{2}$

Dowód indukcyjny:
$1^{\circ}$ $n =1$
$$g(1)\stackrel{zal.rek.}{=} g(0) + \lfloor log_21 \rfloor = 0 = \frac{(1+\lfloor log_21 \rfloor)\lfloor log_21 \rfloor}{2}$$

$2^{\circ}$ Załóżmy, że dla każdego $k < n, k \in \Bbb{N\backslash \{0\}}$ zachodzi $g(k) = \frac{(1+\lfloor log_2k \rfloor)\lfloor log_2k \rfloor}{2}$.

- Dla n parzystego mamy:

$$g(n) \stackrel{zal.rek.}{=} g(\lfloor \frac{n}{2} \rfloor) + \lfloor log_2n \rfloor = g(\frac{n}{2}) + \lfloor log_2n \rfloor \stackrel{zał.ind.}{=}$$

$$\frac{(1+\lfloor log_2 \frac{n}{2} \rfloor)\lfloor log_2\frac{n}{2} \rfloor}{2} + \lfloor log_2n \rfloor =$$

$$\frac{(1+\lfloor log_2n - 1 \rfloor)\lfloor log_2n - 1 \rfloor}{2} + \lfloor log_2n \rfloor =$$

$$\frac{(\lfloor log_2n \rfloor)^2 - \lfloor log_2n \rfloor + 2 \lfloor log_2n \rfloor}{2} =$$

$$\frac{(1+\lfloor log_2n \rfloor)\lfloor log_2n \rfloor}{2}$$

- Dla n nieparzystego mamy:

$$g(n) \stackrel{zal.rek.}{=} g(\lfloor \frac{n}{2} \rfloor) + \lfloor log_2n \rfloor =
g(\frac{n-1}{2}) + \lfloor log_2n \rfloor \stackrel{zał.ind.}{=}$$

$$\frac{(1+\lfloor log_2 \frac{n-1}{2} \rfloor)\lfloor log_2\frac{n-1}{2} \rfloor}{2} + \lfloor log_2n \rfloor = $$

$$\frac{(\lfloor log_2(n-1) \rfloor)^2 - \lfloor log_2(n-1) \rfloor + 2 \lfloor log_2n \rfloor}{2} =$$

Zauważmy, że dla nieparzystych n zachodzi:
$$\lfloor log_2(n-1) \rfloor = \lfloor log_2n \rfloor$$

Uzasadnienie:
Niech $\lfloor log_2n \rfloor = l, l,n \in \Bbb{N \backslash \{0,1\}}$ i $n$ nieparzyste.

Wiemy, że $log_2n \neq l$ (n jest nieparzyste, więc $n \neq 2^l$).

Ponieważ $\lfloor log_2n \rfloor = l$ i $n \neq 2^l \space$ to $\space2^l < n < 2^{l+1}$.

Czyli $\space2^l-1 < n-1 < 2^{l+1}-1 \iff 2^l \leq n-1 < 2^{l+1}$.

Po nałożeniu logarytmu otrzymujemy $l \leq log_2(n-1) < l+1$.

Z definicji podłogi: $\lfloor log_2(n-1) \rfloor = l = \lfloor log_2n \rfloor$.

Zatem

$$g(n)=\frac{(1+\lfloor log_2n \rfloor)\lfloor log_2n \rfloor}{2}$$
Co należało pokazać.

## Zadanie 10

Algorytm jest analogiczny jak dla pojedynczej wieży Hanoi, z tą różnicą, iż zamiast przenieść $n-1$ krążków na słupek C) musimy przenieść ich $2(n-1)$. Następnie przenosimy dwa n-te krążki na słupek B), by potem przenieść $2(n-1)$ krążki ze słupka C) na słupek B).

Zatem wzór rekurencyjny na liczbę potrzebnych ruchów do przestawienia wieży zadanej treścią zadania o $n$ podwójnych krążkach na inny słupek możemy zapisać jako:

$H(n) = H(n-1) + 2 + H(n-1)$

A liczbę kroków potrzebnych do przestawienia tej wieży możemy jawnie określić jako:
$H(n) = 2^{n+1}-2$

Dowód:
$1^{\circ}$ $n = 0 \iff H(0) = 0$

$2^{\circ}$ Załóżmy, że dla każdego $k < m, k \in \Bbb{N}$ zachodzi $H(k) = 2^{k+1}-2$.

$H(n) = H(n-1) + 2 + H(n-1) \stackrel{zał.ind.}{=}
2 \cdot (2^{n}-2) + 2 = 2^{n+1} - 2$

## Zadanie 14

#### a) $F_0 + F_1 + F_2 + ... + F_n = F_{n+2} - 1$

Dowód:
$1^{\circ}$ $n = 0$

$$F_0 = 0 = 1 - 1 = F_2 -1$$

$2^{\circ}$ Załóżmy, że zachodzi $F_0 + F_1 + F_2 + ... + F_k = F_{k+2} - 1$ dla każdego $k < n, k \in \Bbb{N}$.

$$F_0 + F_1 + F_2 + ... + F_{n-1} + F_n \stackrel{zał.ind.}{=}
F_{n+1} - 1 + F_n = F_{n+2} - 1$$

#### b) $F_1 + F_3 + F_5 + ... + F_{2n-1} = F_{2n}$ dla $n \geq 1$

Dowód:
$1^{\circ}$ $n = 1$

$$F_1 = 1 = F_2$$

$2^{\circ}$ Załóżmy, że zachodzi $F_1 + F_3 + ... + F_{2k-1} = F_{2k}$ dla każdego $1 \leq k < n, k \in \Bbb{N}$.

$$F_1 + F_3 + F_5 + ... + F_{2n-3} + F_{2n-1} \stackrel{zał.ind.}{=} F_{2n-2} + F_{2n-1} = F_{2n}$$

#### c) $F_0^2 + F_1^2 + F_2^2 + ... + F_n^2 = F_n F_{n+1}$

Dowód:
$1^{\circ}$ $n = 0$

$$F_0^2 = 0 \cdot 1 = F_0F_1$$

$2^{\circ}$ Załóżmy, że zachodzi $F_0^2 + F_1^2 + F_2^2 + ... + F_k^2 = F_k F_{k+1}$ dla każdego $k < n, k \in \Bbb{N}$.

$$F_0^2 + F_1^2 + F_2^2 + ... + F_{n-1}^2 + F_n^2 \stackrel{zał.ind.}{=}
F_{n-1}F_{n} + F_n^2 =$$

$$F_n(F_n + F_{n-1}) = F_nF_{n+1}$$

#### d) $F_nF_{n+2} = F_{n+1}^2 + (-1)^{n+1}$

Dowód:
$1^{\circ}$ $n = 0$

$$F_0F_2 = 0 = F_1^2 + (-1)^1$$

$2^{\circ}$ Załóżmy, że zachodzi $F_kF_{k+2} = F_{k+1}^2 + (-1)^{k+1}$ dla każdego $k < n, k \in \Bbb{N}$.

$$F_nF_{n+2} = F_n(F_n + F_{n+1}) = F_n^2 + F_nF_{n+1} \stackrel{zał.ind.}{=} F_{n-1}F_{n+1} - (-1)^n + F_nF_{n+1} =$$
$$F_{n+1}(F_{n-1} + F_n) + (-1)^{n+1} =
F_{n+1}^2 + (-1)^{n+1}$$

## Zadanie 15
### I część

Pokażmy, że:

$$Teza: \space F_n = \frac{1}{\sqrt5}\Bigg(\Big(\frac{1 + \sqrt5}{2}\Big)^n - \Big(\frac{1 - \sqrt5}{2}\Big)^n\Bigg)$$

$1^{\circ}$ $n \in \{0, 1\}$

$$F_0 = 0 = \frac{1}{\sqrt5}\Bigg(\Big(\frac{1 + \sqrt5}{2}\Big)^0 - \Big(\frac{1 - \sqrt5}{2}\Big)^0\Bigg)$$

$$F_1 = 1 = \frac{1}{\sqrt5} \frac{2\sqrt5}{2} = \frac{1}{\sqrt5}\Bigg(\Big(\frac{1 + \sqrt5}{2}\Big)^1 - \Big(\frac{1 - \sqrt5}{2}\Big)^1\Bigg)$$

$2^{\circ}$ Załóżmy, że teza zachodzi dla $F_{n-1}$, $F_n$.

$$F_{n+1} = F_{n-1} + F_{n} \stackrel{zał.ind.}{=}$$

$$\frac{1}{\sqrt5}\Bigg(
\Big(\frac{1 + \sqrt5}{2}\Big)^{n-1} - \Big(\frac{1 - \sqrt5}{2}\Big)^{n-1} +
\Big(\frac{1 + \sqrt5}{2}\Big)^n - \Big(\frac{1 - \sqrt5}{2}\Big)^n
\Bigg)=$$

$$\frac{1}{\sqrt5}\Bigg(
\Big(\frac{1 + \sqrt5}{2}\Big)^n \Big( \frac{2}{1+\sqrt5} + 1 \Big) -
\Big(\frac{1 - \sqrt5}{2}\Big)^n \Big( \frac{2}{1-\sqrt5} + 1 \Big)
\Bigg)=$$

$$\frac{1}{\sqrt5}\Bigg(
\Big(\frac{1 + \sqrt5}{2}\Big)^n \Big( \frac{3 + \sqrt5}{1+\sqrt5}\Big)\Big(\frac{1 - \sqrt5}{1-\sqrt5} \Big) -
\Big(\frac{1 - \sqrt5}{2}\Big)^n \Big( \frac{3 - \sqrt5}{1-\sqrt5}\Big)\Big(\frac{1 + \sqrt5}{1+\sqrt5} \Big)
\Bigg)=$$

$$\frac{1}{\sqrt5}\Bigg(
\Big(\frac{1 + \sqrt5}{2}\Big)^n \Big( \frac{1 + \sqrt5}{2}\Big) -
\Big(\frac{1 - \sqrt5}{2}\Big)^n \Big( \frac{1 - \sqrt5}{2}\Big)
\Bigg)=$$

$$\frac{1}{\sqrt5}\Bigg(
\Big(\frac{1 + \sqrt5}{2}\Big)^{n+1} -
\Big(\frac{1 - \sqrt5}{2}\Big)^{n+1}
\Bigg)$$

Co należało pokazać.

### II część

Dla jakich n mamy $F_n = \Big\lfloor \frac{1}{\sqrt5}
\Big( \frac{1 + \sqrt5}{2} \Big)^n + \frac{1}{2} \Big\rfloor?$

Są to takie n, które spełniają nierówność (korzystamy ze wzoru na $F_n$ udowodnionego powyżej):

$$F_n \leq
\frac{1}{\sqrt5} \Big( \frac{1 + \sqrt5}{2} \Big)^n + \frac{1}{2}
< F_n + 1 \Bigg/ - \frac{1}{\sqrt5} \Big( \frac{1 + \sqrt5}{2} \Big)^n$$

$$ -\frac{1}{\sqrt5}\Big(\frac{1 - \sqrt5}{2}\Big)^{n} \leq
\frac{1}{2}
< -\frac{1}{\sqrt5}\Big(\frac{1 - \sqrt5}{2}\Big)^{n} + 1
\Bigg/ + \frac{1}{\sqrt5} \Big( \frac{1 - \sqrt5}{2} \Big)^n$$

$$0 \leq
\frac{1}{2} + \frac{1}{\sqrt5} \Big( \frac{1 - \sqrt5}{2} \Big)^n
< 1$$

$$-\frac{\sqrt5}{2} \leq
\Big( \frac{1 - \sqrt5}{2} \Big)^n
< \frac{\sqrt5}{2}$$

Zauważmy, że $\Big( \frac{1 - \sqrt5}{2} \Big)^n = q^n$ ciąg geometryczny, taki że $|q| < 1$ i jest zbieżny (dla n dążących do nieskończoności) do zera.

Dla $n = 0 \space$ mamy:

$$-\frac{\sqrt5}{2} \leq
\Big( \frac{1 - \sqrt5}{2} \Big)^0 = 1
< \frac{\sqrt5}{2}$$

Ponieważ $|q^n| > |q^{n+1}|$ to nierówność zachodzi dla każdego $n \in \Bbb{N}$.

###### tags: `mdm`