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

# Lista 2

## 1

$a \notin \mathbb{Q}$
$n \in \mathbb{Z} _+$
$a \notin \mathbb{Q} \Rightarrow an \notin \mathbb{Q} \Rightarrow an \notin \mathbb{Z}$

Załóżmy więc, że {an} = x, gdzie x $\neq$ 0.

Teza: $\lfloor an\rfloor + \lfloor (1-a)n)\rfloor = n - 1$

Dowód:

$1 = 1$
$an + 1 - x - an + x = 1$
$an + (1 - x) - ( an - x) = 1$

x = {an}, więc $an + (1 - x) = \lceil an\rceil$ oraz $an - x = \lfloor an\rfloor$

$\lceil an\rceil - \lfloor an\rfloor = 1$ / $\times (-1)$
$\lfloor an\rfloor - \lceil an\rceil = - 1$
$\lfloor an\rfloor + \lfloor - an\rfloor = - 1$ / $+n$
$\lfloor an\rfloor + n + \lfloor - an\rfloor = n - 1$
$\lfloor an\rfloor + \lfloor n - an\rfloor = n - 1$
$\lfloor an\rfloor + \lfloor (1-a)n)\rfloor = n - 1$
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\blacksquare$

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

Dowód:

$-1 = -1$
$an - x - an + x - 1 = -1$
$an - x - (an + 1- x) = -1$

x = {an}, więc $an + (1 - x) = \lceil an\rceil$ oraz $an - x = \lfloor an\rfloor$

$\lfloor an\rfloor - \lceil an\rceil = - 1$ / $\times (-1)$
$\lceil an\rceil - \lfloor an\rfloor = 1$
$\lceil an\rceil + \lceil - an\rceil = 1$ / $+n$
$\lceil an\rceil + n + \lceil - an\rceil = n + 1$
$\lceil an\rceil + \lceil n - an)\rceil = n + 1$
$\lceil an\rceil + \lceil (1-a)n)\rceil = n + 1$
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\blacksquare$

## 3
### a)
Do określenia jednoznacznie ciągu $a_n = na_{n-2}$ potrzebujemy 2 elementów początkowych.
**1$^\circ$**
2 elementy wystarczą, ponieważ znając $a_0$ i $a_1$ policzymy $a_2$ (wykorzystując element $a_0$), policzymy $a_3$ (wykorzystując element $a_1$), policzymy $a_4$ (wykorzystując element $a_2$) i tak każdy następny.

**2$^\circ$**
1 element nie wystarczy, ponieważ znając tylko $a_0$ policzymy $a_2$ (wykorzystując element $a_0$), ale nie policzymy już $a_1$ ani $a_3$ gdyż nie znamy $a_{1}$. Wtedy będziemy mogli policzyć tylko elementy parzyste tego ciągu.

### b)
Do określenia jednoznacznie ciągu $a_n = a_{n-1} + a_{n-3}$ potrzebujemy 3 elementów początkowych.

**1$^\circ$**
3 elementy wystarczą, ponieważ znając $a_0$, $a_1$ i $a_2$ policzymy $a_3$ (wykorzystując element $a_0$ i $a_2$), policzymy $a_4$ (wykorzystując element $a_1$ i $a_3$), policzymy $a_5$ (wykorzystując element $a_2$ i $a_4$), policzymy $a_6$ (wykorzystując element $a_3$ i $a_5$)i tak każdy następny.

**2$^\circ$**
2 elementy nie wystarczą, ponieważ znając tylko $a_0$ i $a_1$ nie jesteśmy w stanie policzyć ani $a_2$, ani $a_3$, ani żadnego innego elementu.
### c)
Do określenia jednoznacznie ciągu $a_n = 2a_{\lfloor \frac{n}{2}\rfloor} + n$ nie potrzebujemy znać wcześniej żadnego elementu.
$a_0 = 2a_{\lfloor \frac{0}{2}\rfloor} + 0$
$a_0 = 2a_{\lfloor \frac{0}{2}\rfloor}$
$a_0 = 2a_0$
$a_0 = 0$
$a_1 = 2a_{\lfloor \frac{1}{2}\rfloor} + 1 = 2a_0 + 1 = 1$
$a_2 = 2a_{\lfloor \frac{2}{2}\rfloor} + 2 = 2a_1 + 2 = 2 + 2 = 4$
i tak dalej można obliczyć każdy następny element.
## 4

### a)
$f_n =f_{n-1} + 3^n$ dla $n > 1$ i $f_1 = 3$

Moja teza: $f_n = \displaystyle\sum_{i=1}^{n}3^i$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n = 1
L = $f_1$ = 3
P = $\displaystyle\sum_{i=1}^{1}3^i = 3^1 = 3$
L = P

**2$^\circ$** Załóżmy, że $f_n = \displaystyle\sum_{i=1}^{n}3^i$, rozpatrzmy przypadek dla n+1

$f_{n+1} = f_{n} + 3^{n+1} =$ (Z założenia indukcyjnego) $\displaystyle\sum_{i=1}^{n}3^i + 3^{n+1} = \displaystyle\sum_{i=1}^{n+1}3^i$
Na podstawie indukcji matematycznej udowodniłem, że $f_n = \displaystyle\sum_{i=1}^{n}3^i$ dla $n > 1$ i $f_1 = 3$.

Z sumy ciągu geometrycznego $\displaystyle\sum_{i=1}^{n}3^i = 3\times\frac{1-3^n}{1-3} = 3\times\frac{3^n - 1}{2}$.
Stąd $f_n = 3\times\frac{3^n - 1}{2}$

### b)
$h_n =h_{n-1} + (-1)^{n+1}$ dla $n > 1$ i $h_1 = 1$
Moja teza: $h_n =\frac{(-1)^{n+1} + 1}{2}$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n = 1
L = $h_1$ = 1
P = $\frac{(-1)^{1+1} + 1}{2} = \frac{(-1)^{2} + 1}{2} = \frac{1 + 1}{2} = 1$
L = P

**$2^\circ$** Załóżmy, że $h_n = \frac{(-1)^{n+1} + 1}{2}$, rozpatrzmy przypadek dla n+1

$h_{n+1} = h_n + (-1)^{n+2} = h_n + (-1)^n =$ (Z założenia indukcyjnego) $\frac{(-1)^{n+1} + 1}{2} + (-1)^n = \frac{(-1)^{n+1} + 1 + 2(-1)^n}{2} = \frac{-(-1)^{n+2} + 1 + 2(-1)^{n+2}}{2} = \frac{(-1)^{n+2}(-1 + 2) + 1}{2} = \frac{(-1)^{n+2} + 1}{2}$

Na podstawie indukcji matematycznej udowodniłem, że $h_n = \frac{(-1)^{n+1} + 1}{2}$.

Dla n parzystego $h_n = \frac{(-1)^{n+1} + 1}{2} = \frac{-1 + 1}{2} = 0$
Dla n nieparzystego $h_n = \frac{(-1)^{n+1} + 1}{2} = \frac{1 + 1}{2} = 1$

Czyli inaczej mówiąc

**$h_n$**=\begin{cases}
0 & \quad \text{dla } n \text{ parzystego}\\
1 & \quad \text{dla } n \text{ nieparzystego}
\end{cases}

### c)
$l_n = l_{n-1}l_{n-2}$ dla $l > 2$ i $l_1 = l_2 = 2$
Moja teza: $l_n = 2^{\frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)}$ inaczej mówiąc $l_n = 2^{F_n}$

Dowód:
L = $l_n = l_{n-1}l_{n-2}$ = P
L = $l_n = 2^{log_2(l_n)}$
P = $l_{n-1}l_{n-2} = 2^{log_2(l_{n-1}l_{n-2})} = 2^{log_2(l_{n-1}) + log_2(l_{n-2})}$

Wiemy, że $F_n = F_{n-1} + F_{n-2}$ gdzie $F_1 = F_2 = 1$ (Ciąg Fibonacciego)
Zauważmy, że $log_2(l_2) = log_2(l_1) = 1 = F_1 = F_2$
czyli $log_2(l_n) = log_2(l_{n-1}) + log_2(l_{n-2})$

co dowodzi, że $l_n = 2^{F_n}$

korzystając z ze wzoru na n-tą liczbę ciągu Fibonacciego
$F_n = \frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)$
Czyli
$l_n =2^{\frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)}$
$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\blacksquare$

## 5
### a)
$a_0 = 1$, $a_n = 2/a_{n-1}$
Moja teza: $a_n = \frac{(-1)^{n+1} + 3}{2}$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n = 0
L = $a_0$ = 1
P = $\frac{(-1)^{0+1} + 3}{2} = \frac{(-1)^{1} + 3}{2} = \frac{-1 + 3}{2} = \frac{2}{2} = 1$
L = P

**$2^\circ$** Załóżmy, że $a_n = \frac{(-1)^{n+1} + 3}{2}$, rozpatrzmy przypadek dla n+1

$a_{n+1} = \frac{2}{a_n} =$ z założenia indukcyjnego $= \frac{2}{\frac{(-1)^{n+1} + 3}{2}} = 2 \times \frac{2}{(-1)^{n+1} + 3} = \frac{4}{(-1)^{n+1} + 3}$

Rozpatrzmy dwa przypadki:
**1$^{\circ\circ}$** Dla n parzystego
$\frac{4}{(-1)^{n+1} + 3} = \frac{4}{-1 + 3} = \frac{4}{2} = 2$, według wzoru $a_{n+1} = \frac{(-1)^{n+2} + 3}{2} = \frac{1 + 3}{2} = \frac{4}{2} = 2$ dla n parzystego równość zachodzi

**2$^{\circ\circ}$** Dla n nieparzystego
$\frac{4}{(-1)^{n+1} + 3} = \frac{4}{1 + 3} = \frac{4}{4} = 1$, według wzoru $a_{n+1} = \frac{(-1)^{n+2} + 3}{2} = \frac{-1 + 3}{2} = \frac{2}{2} = 1$ dla n nieparzystego równość zachodzi

Czyli z tego że równość zachodzi dla nieparzystego n i parzystego n wynika, że równość zachodzi dla każdego n > 0.

Na podstawie indukcji matematycznej udowodniłem, że $a_n = \frac{(-1)^{n+1} + 3}{2}$

Dla n parzystego $a_n = \frac{(-1)^{n+1} + 3}{2} = \frac{-1 + 3}{2} = 1$
Dla n nieparzystego $a_n = \frac{(-1)^{n+1} + 3}{2} = \frac{1 + 3}{2} = 2$

Czyli inaczej mówiąc

**$a_n$**=\begin{cases}
1 & \quad \text{dla } n \text{ parzystego}\\
2 & \quad \text{dla } n \text{ nieparzystego}
\end{cases}

### b)

$b_0 = 0, b_n = 1/(1+b_{n-1})$

Moja teza: $b_n = \frac{F_{n}}{F_{n+1}}$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n=0

L = 0
P = $\frac{F_0}{F_1} = \frac{0}{1} = 0$
L = P

**2$^\circ$** Załóżmy, że $b_n = \frac{F_{n}}{F_{n+1}}$, rozpatrzmy przypadek dla n+1

$b_{n+1} = \frac{1}{1 + b_{n}} =$ Z założenia indukcyjnego $=\frac{1}{1 + \frac{F_{n}}{F_{n+1}}} = \frac{F_{n+1}}{F_{n+1} + F_{n}} = \frac{F_{n+1}}{F_{n+2}}$

Na podstawie indukcji matematycznej udowodniłem, że $b_n = \frac{F_{n}}{F_{n+1}}$

(jeżeli taka forma odpowiedzi jest nie wystarczająca, podany ułamek $\frac{F_{n}}{F_{n+1}}$ można rozpisać podobnie jak to zrobiłem w zadaniu 4 w podpunkcie c według wzoru, który udowodniłem w zadaniu 15)

### c)

$c_0 = 1, c_n = \displaystyle\sum_{i=0}^{n-1}c_i$
Moja teza: $c_n = 2^{n-1}$ dla n > 0 i 1 dla n = 0

Czyli inaczej mówiąc

**$c_n$**=\begin{cases}
1 & \quad \text{dla } n = 0\\
2^{n-1} & \quad \text{dla } n > 0
\end{cases}

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n=1
L = $\displaystyle\sum_{i=0}^{0}c_i = c_0 = 1$
P = $2^{1-1} = 2^0 = 1$
L = P

**$2^\circ$** Załóżmy, że $c_n = 2^{n-1}$ dla każdego 1 < n < t, rozpatrzmy przypadek dla t
$c_{t} = \displaystyle\sum_{i=0}^{t-1}c_i = \displaystyle\sum_{i=1}^{t-1}2^{i-1} + c_0 = \displaystyle\sum_{i=1}^{t-1}2^{i-1} + 1 = 1 + \frac{1 - 2^{t-1}}{1-2} = 1+ 2^{t-1} - 1 = 2^{t-1}$

Na podstawie indukcji matematycznej udowodniłem, że dla n > 1 $c_n = 2^{n-1}$.

### d)

$d_0 = 1, d_1 = 2, d_n = d_{n-1}^2/d_{n-2}$
Moja teza: $d_n = 2^n$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n=0, n=1
**1$^{\circ\circ}$** dla n=0
L = $d_0$ = 1
P = $2^0$ = 1
P = L
**2$^{\circ\circ}$** dla n=1
L = $d_1$ = 2
P = $2^{1}$ = 2
L = P

**2$^\circ$** Załóżmy, że $d_n = 2^n$ oraz $d_{n-1} = 2^{n-1}$, rozpatrzmy przypadek dla n+1

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

Na podstawie indukcji matematycznej udowodniłem, że $d_n = 2^n$.

## 6

### a)
$y_0 = y_1 = 1, y_n = \frac{y_{n-1}^2 + y_{n-2}}{y_{n-1} + y_{n-2}}$

Teza: $y_n = 1$

Dowód przeprowadzę przez indukcję:
**1$^\circ$** Dla n = 2, n=3
**1$^{\circ\circ}$** n = 2
L = $y_2 =\frac{y_{1}^2 + y_{0}}{y_{1} + y_{0}} = \frac{1^2+1}{1+1} = 1$
P = 1
L = P
**2$^{\circ\circ}$** n = 3
L = $y_3 =\frac{y_{2}^2 + y_{1}}{y_{2} + y_{1}} = \frac{1^2+1}{1+1} = 1$
P = 1
L = P
**2$^\circ$** Załóżmy, że $y_n = 1$ oraz $y_{n-1} = 1$, rozpatrzmy przypadek dla n+1

$\frac{y_{n}^2 + y_{n-1}}{y_{n} + y_{n-1}} = \frac{1^2+1}{1+1} = 1$

Na podstawie indukcji matematycznej udowodniłem, że $y_n = 1$
### b)
$z_0 = 1, z_1 = 2, z_n = \frac{z_{n-1}^2-1}{z_{n-2}}$

Teza: $z_n = n + 1$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n = 2, n=3
**1$^{\circ\circ}$** n = 2
L = $\frac{z_{1}^2-1}{z_{0}} =\frac{2^2-1}{1} = \frac{3}{1} = 3$
P = 2 + 1 = 3
L = P
**2$^{\circ\circ}$** n = 3
L = $\frac{z_{2}^2-1}{z_{1}} =\frac{3^2-1}{2} = \frac{8}{2} = 4$

P = 3 + 1 = 4
L = P

**2$^\circ$** Załóżmy, że $z_n = n + 1$ oraz $z_{n-1} = n$, rozpatrzmy przypadek dla n+1

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

Na podstawie indukcji matematycznej udowodniłem, że $z_n = n + 1$

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

Teza: $t_n = n^2$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n = 2, n=3
**1$^{\circ\circ}$** n = 2
L = $\frac{(t_{1} - t_{0}+3)^2}{4} = \frac{4^2}{4} = 4$
P = $2^2 = 4$
L = P

**2$^{\circ\circ}$** n = 3
L = $\frac{(t_{2} - t_{1}+3)^2}{4} = \frac{6^2}{4} = 9$
P = $3^2 = 9$
L = P

**2$^\circ$** Załóżmy, że $t_n = n^2$ oraz $t_{n-1} = (n-1)^2$, rozpatrzmy przypadek dla n+1

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

Na podstawie indukcji matematycznej udowodniłem, że $t_n = n^2$.
## 8

$a_{n} = \frac{1+a_{n-1}}{a_{n-2}}$ gdzie $a_{0}=\alpha, a_{1}=\beta$

$a_{2}=\frac{1+\beta}{\alpha}$

$a_{3}= \frac{1 + \frac{1 + \beta}{\alpha}}{\beta} = \frac{1+\alpha+\beta}{\alpha \beta}$

$a_{4}= \frac{1+a_3}{a_2} = \frac{1+\frac{1+\alpha+\beta}{\alpha \beta}}{\frac{1+\beta}{\alpha}} = \frac{\alpha+\frac{1+\alpha+\beta}{ \beta}}{1+\beta} = \frac{\alpha\beta + 1 + \alpha + \beta}{\beta + \beta^2} = \frac{(\alpha + 1)(\beta + 1)}{\beta(\beta + 1)} = \frac{\alpha + 1}{\beta}$

$a_{5}=\frac{1 + a_4}{a_3} = \frac{1 + \frac{\alpha + 1}{\beta}}{\frac{1+\alpha+\beta}{\alpha \beta}} = \frac{\alpha\beta + \alpha^2 + \alpha}{1+\alpha+\beta} = \frac{\alpha(\beta + \alpha + 1)}{1+\alpha+\beta} = \alpha$

$a_{6}=\frac{1 + a_5}{a_4} =\frac{1 + \alpha}{\frac{\alpha + 1}{\beta}} = \beta$

$a_{7} = \frac{1 + a_6}{a_5} = \frac{1+\beta}{\alpha} = \frac{1 + a_1}{a_0} = a_{2}$
$a_{8} = \frac{1 + a_7}{a_6} = \frac{1 + a_2}{a_1} = a_3$

Jak można zuważyć wyniki się zapętlają, więc

**$a_n$**=\begin{cases}
\alpha & \quad \text{dla } n \text{ podzielnego przez 5}\\
\beta & \quad \text{dla } n \text{ dającego resztę 1 przy dzieleniu przez 5}\\
\frac{1+\beta}{\alpha}
& \quad \text{dla } n \text{ dającego resztę 2 przy dzieleniu przez 5}\\
\frac{1+\alpha+\beta}{\alpha \beta}
& \quad \text{dla } n \text{ dającego resztę 3 przy dzieleniu przez 5}\\
\frac{\alpha + 1}{\beta} & \quad \text{dla } n \text{ dającego resztę 4 przy dzieleniu przez 5}
\end{cases}

Aby ciąg był określony dla wszystich n, $\alpha$ i $\beta$ muszą spełniać poniższe założenia:

$\alpha \neq 0$
$\alpha \neq -1$
$\beta \neq 0$
$\beta \neq -1$
$\alpha + \beta \neq -1$

## 14

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

Dowód przeprowadzę przez indukcję:
**1$^\circ$** Dla n=0
L = $F_0 = 0$
P = $F_{0+2} - 1 = F_2 - 1 = 1 - 1 = 0$
L = P

**2$^\circ$** Załóżmy, że $F_0 + F_1 + F_2 + ... + F_n = F_{n+2} - 1$, rozpatrzmy przypadek dla n+1

L = $F_0 + F_1 + F_2 + ... + F_n + F_{n+1} =$ z założenia indukcyjnego $= F_{n+2} - 1 + F_{n+1} = F_{n+3} - 1$

Na podstawie indukcji matematycznej udowodniłem, że $F_0 + F_1 + F_2 + ... + F_n = F_{n+2} - 1$

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

Dowód przeprowadzę przez indukcję:
**1$^\circ$** Dla n=1
L = $F_1 = 1$
P = $F_{2\times1}= F_2 = 1$
L = P

**2$^\circ$** Załóżmy, że $F_1 + F_3 + F_5 + ... + F_{2n-1} = F_{2n}$ Dla n $\geq$ 1, rozpatrzmy przypadek dla n+1

L = $F_1 + F_3 + F_5 + ... + F_{2n-1} + F_{2n + 1}=$ z założenia indukcyjnego $=F_{2n} + F_{2n + 1} = F_{2n+2} = F_{2(n+1)}$

Na podstawie indukcji matematycznej udowodniłem, że $F_1 + F_3 + F_5 + ... + F_{2n-1} = F_{2n}$

### c)

Teza: $F_0^2 + F_1^2 + F_2^2 + ... + F_n^2 = F_nF_{n+1}$

Dowód przeprowadzę przez indukcję:
**1$^\circ$** Dla n=0
L = $F_0^2 = 0^2 = 0$
P = $F_nF_{n+1}= F_0F_{n+1} = 0\times1 = 0$
L = P

**2$^\circ$** Załóżmy, że $F_0^2 + F_1^2 + F_2^2 + ... + F_n^2 = F_nF_{n+1}$, rozpatrzmy przypadek dla n+1

L = $F_0^2 + F_1^2 + F_2^2 + ... + F_n^2 + F_{n+1}^2 =$ z założenia indukcyjnego $= F_nF_{n+1} + F_{n+1}^2 = F_{n+1}(F_n + F_{n+1}) = F_{n+1}F_{n+2}$

Na podstawie indukcji matematycznej udowodniłem, że $F_0^2 + F_1^2 + F_2^2 + ... + F_n^2 = F_nF_{n+1}$

### d)

Teza: $F_nF_{n+2} = F_{n+1}^2 + (-1)^{n+1}$

Dowód przeprowadzę przez indukcję:
**1$^\circ$** Dla n=0
L = $F_0F_{0+2} = F_0F_2 = 0\times1 = 0$
P = $F_{0+1}^2 + (-1)^{0+1} = F_1^2 + (-1)^1 = 1^2 - 1 = 1 - 1 = 0$
L = P

**2$^\circ$** Załóżmy, że $F_nF_{n+2} = F_{n+1}^2 + (-1)^{n+1}$, rozpatrzmuy przypadek n+1

L = $F_{n+1}F_{n+3} = F_{n+1}(F_{n+1}+F_{n+2}) = F_{n+1}^2 + F_{n+1}F_{n+2} =$ z założenia indukcyjnego $= F_{n+1}F_{n+2} + F_nF_{n+2} - (-1)^{n+1} = F_{n+1}F_{n+2} + F_nF_{n+2} + (-1)^{n+2} = F_{n+2}(F_{n+1} + F_n) + (-1)^{n+2} = F_{n+2}F_{n+2} + (-1)^{n+2} = F_{n+2}^2 + (-1)^{n+2}$

Na podstawie indukcji matematycznej udowodniłem, że $F_nF_{n+2} = F_{n+1}^2 + (-1)^{n+1}$.

## 15

Teza: $F_n = \frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** Dla n=0, n=1
**1$^{\circ\circ}$** dla n=0
L = $F_0$ = 0
P = $\frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^0 - (\frac{1-\sqrt{5}}{2})^0) = \frac{1}{\sqrt5} \times (1 - 1) = 0$
P = L
**2$^{\circ\circ}$** dla n=1
L = $F_1$ = 1
P = $\frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^1 - (\frac{1-\sqrt{5}}{2})^1) = \frac{1}{\sqrt5}\times \frac{1 + \sqrt{5} - 1 + \sqrt{5}}{2} = \frac{1}{\sqrt5}\times \frac{2\sqrt{5}}{2} = 1$
L = P

**2$^\circ$** Załóżmy, że $F_n = \frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)$ oraz $F_{n-1} = \frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^{n-1} - (\frac{1-\sqrt{5}}{2})^{n-1})$, rozpatrzmy przypadek dla n+1

$F_{n+1} = F_{n} + F_{n-1} =$ z założenia indukcyjnego $= \frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n) + \frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^{n-1} - (\frac{1-\sqrt{5}}{2})^{n-1}) = \frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n + (\frac{1+\sqrt{5}}{2})^{n-1} - (\frac{1-\sqrt{5}}{2})^{n-1}) =$$=\frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^{n-1}(1 + \frac{1+\sqrt{5}}{2}) - (\frac{1-\sqrt{5}}{2})^{n-1}(1 + \frac{1-\sqrt{5}}{2})) = \frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^{n-1}(\frac{3+\sqrt{5}}{2}) - (\frac{1-\sqrt{5}}{2})^{n-1}(\frac{3-\sqrt{5}}{2})) =$$=\frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^{n-1}(\frac{6+2\sqrt{5}}{4}) - (\frac{1-\sqrt{5}}{2})^{n-1}(\frac{6-2\sqrt{5}}{4})) = \frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^{n-1}(\frac{5+2\sqrt{5} + 1}{4}) - (\frac{1-\sqrt{5}}{2})^{n-1}(\frac{5-2\sqrt{5} + 1}{4})) =$$=\frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^{n-1}(\frac{(1+\sqrt{5})^2}{2^2}) - (\frac{1-\sqrt{5}}{2})^{n-1}(\frac{(1-\sqrt{5})^2}{2^2})) = \frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^{n-1}(\frac{1+\sqrt{5}}{2})^2 - (\frac{1-\sqrt{5}}{2})^{n-1}(\frac{1-\sqrt{5}}{2})^2) =$$=\frac{1}{\sqrt5}((\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1})$

Na podstawie indukcji matematycznej udowodniłem, że $F_n = \frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)$.

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

Inaczej mówiąc
Dla jakich n:
|$\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n| \leq \frac{1}{2}$ (ponieważ jeżeli ta równość zachodzi, to zaokrąglenie poprzez podłogę zawsze zwróci n-tą liczbę ciągu Fibonacciego)

dla n=0
$L = |\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^0| = \frac{1}{\sqrt{5}} \leq \frac{1}{2}$
Im większy jest n, tym mniejsza jest wartość po lewej stronie nierówności (ciąg $x_n =$ |$\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$| jest monotoniczny i maleje), więc jeżeli dla $n_0$ nierówność |$\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n| \leq \frac{1}{2}$ jest prawdziwa to dla każdego większego n, ta nierówność również będzie prawdziwa. Z tego wynika, że dla
$\forall_{n \geq 0, n \in \mathbb{N}}$ $F_n = \lfloor\frac{1}{\sqrt5}\times((\frac{1+\sqrt{5}}{2})^n + \frac{1}{2}\rfloor$