====== Matematyka dyskretna (M) - Lista 2. ======

===== Zadanie 1. =====

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

Dla powały analogicznie; wychodzi n+1.

===== Zadanie 2. =====
===== Zadanie 3. =====
===== Zadanie 4. =====

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

 stosując metodę iteracyjną, mamy:

 $f_n = 3^n + f_{n-1} = 3^n + 3^{n-1} + f_{n-2} = ... = 3^n + 3^{n-1} + 3^{n-2} + ... + 3^2 + 3 = \frac{3^{n+1}-1}{3-1} = \frac{1}{2}\cdot(3^{n+1}-1)$


**b)**


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

 znowu wystarczy trochę rozwinąć:

 $l_n = l_{n-1}l_{n-2} = (l_{n-2}\cdot l_{n-3})\cdot l_{n-2} = (l_{n-2}\cdot l_{n-2})\cdot l_{n-3} =$\\ 


 $(l_{n-3}\cdot l_{n-3}\cdot l_{n-4}\cdot l_{n-4})\cdot l_{n-3} = \underbrace{(l_{n-3}\cdot l_{n-3}\cdot l_{n-3})}_{3\;\rm times}\cdot\underbrace{l_{n-4}\cdot    
 l_{n-4}}_{2\;\rm times}  =$\\


 $= (l_{n-4}\cdot l_{n-4}\cdot l_{n-4}\cdot l_{n-5}\cdot l_{n-5}\cdot l_{n-5})\cdot l_{n-4}\cdot l_{n-4} = \underbrace{(l_{n-4}\cdot l_{n-4}\cdot l_{n-4}\cdot  
 l_{n-4}\cdot l_{n-4})}_{5\;\rm times}\cdot \underbrace{l_{n-5}\cdot l_{n-5}\cdot l_{n-5}}_{3\;\rm times} =$\\

 $  = ... = l_{n-k}^{F_{k+1}} \cdot l_{n-k-1}^{F_{k}} =$\\


 $  = 2^{F_{n-2}} \cdot 2^{F_{n-1}} = 2^{F_n}  $

===== Zadanie 5. =====
====a)====
$a_0 = 1, a_n = 2 / a_{n-1} $

$a_0 = 1, a_1 = 2, a_2 = 1, a_3 = 2, ...$

Myślę, że wzór to:
$a_n = n\pmod{2} + 1$

Dowód indukcyjny:

Baza:

$n = 0$

$a_0 = 0\pmod{2} + 1 = 1$
OK

Krok:
$a_{n+1} = \frac{2}{n\pmod{2} + 1}$

Dla parzystych:
$a_{n+1} = \frac{2}{1} = 2 = n+1\pmod{2} + 1$

Dla nieparzystych:
$a_{n+1} = \frac{2}{2} = 1 = n+1\pmod{2} + 1$

===== Zadanie 6. =====

**a)**
$y_0 = y_1 = 1; y_n = \frac{y^2_{n-1} + y_{n-2}}{y_{n-1}+y_{n-2}}$
kilka pierwszych elementów: 1, 1, 1, 1...
zgadujemy, że $y_n = 1$
sprawdzamy $y_n = \frac{1+1}{1+1} = 1$ 

**b)**
$z_0 = 1, \ z_1 = 2; z_n = \frac{z^2_{n-1}-1}{z_{n-2}}$
ta sama metoda, pierwsze elementy: 1, 2, 3, 4, 5...
oo zgadujemy, że $z_n = n+1$
sprawdzmy $z_n = \frac{(n^2-1}{n-1} = \frac{(n+1)(n-1)}{n-1} = n+1$


**c)**
$t_0 = 0, t_1 = 1; t_n = \frac{(t_{n-1} - t_{n-2} +3)^2}{4}$
pierwsze elementy: 0, 1, 4, 9, 16, 25...
oo zgadujemy, że $z_n = n^2$
sprawdzmy $z_n = \frac{((n-1)^2 - (n-2)^2 +3)^2}{4} = \frac{4n^2}{4} = n^2$

===== Zadanie 7. =====

====a)====

$a_0 = 1$; $a_1 = 1+1$; $a_2 = 2+2+1$; $a_3 = 3\cdot2+3\cdot2+3+1$; $a_4 = 4\cdot3\cdot2+4*3\cdot2+4\cdot3+4+1$. \\

$a_n = \displaystyle 1 + \sum_{i=0}^{n-1}{\frac{n!}{i!}}$

//Dowód//

Dla $n = 0$: $a_0 = 1$. OK.

Dla $n > 0$: $\displaystyle a_n = na_{n-1} + 1 = n \cdot (1 + \sum_{i=0}^{n-2}{\frac{(n-1)!}{i!}}) + 1 = n + \sum_{i=0}^{n-2}{\frac{n!}{i!}} + 1 = 1 + \sum_{i=0}^{n-1}{\frac{n!}{i!}}$. OK.

====b)====

$b_0 = 1/2; b_1 = 1/2; b_2 = 1/2;$\\
$b_3 = 1/(2*3) + 1/3;$\\
$b_4 = 2/(2*3*4) + 2/(3*4) + 1/4;$\\
$b_5 = 2*3/(2*3*4*5) + 2*3/(3*4*5) + 3/(4*5) + 1/5$\\
$b_6 = 2*3*4/(2*3*4*5*6) + 2*3*4/(3*4*5*6) + 3*4/(4*5*6) + 4/(5*6) + 1/6$\\

Zatem

$b_n = \displaystyle \sum_{i=0}^{n-2}{ \frac{ (n-2)! \cdot (i+1)! }{ n! \cdot i! } } = \frac{(n-2)!}{n!} \sum_{i=0}^{n-2}{(i+1)} = \frac{(n-1)n}{n\cdot(n-1)\cdot2} = \frac 1 2$  

//Dowód//

$n = 2$. $b_2 = 1/2$. OK. \\
$n > 2$. $\displaystyle b_n = \frac{(n-2)b_{n-1} + 1}{n} =  \frac{(n-2)\frac 1 2 + 1}{n} = \frac 1 2$. OK.

====c)====

$c_0 = 0$\\
$c_1 = 1 + 2$\\
$c_2 = 4*1/2 + 4*2/2 + 2/2 + 2/2$\\
$c_3 = 5*4*1/(2*3) + 5*4*2/(2*3) + 5*2/(2*3) + 5*2/(2*3) + 3/3 + 2/3$\\
$c_4 = 6*4*1/(2*3*4) + 6*5*4*2(2*3*4) + 6*5*2/(2*3*4) + 6*5*2/(2*3*4) + 6*3/(3*4) + 6*2/(3*4) + 4/4 + 2/4$\\

cdn.

====d)====

$d_0 = 1; d_1 = 2$\\
$d_2 = 1$
$d_3 = 2/3$
$d_4 = 2!/4 * 2/(3*4)$
$d_5 = 3!*2!*2*2 / (3*3*4*5)$
$d_6 = 4!*3!*2!*2!*2*2*2 / (3*3*3*4*4*4*5*6)$
$d_7 = 5!*4!*3!*3!*2!*2*2*2!*2!*2*2*2 / (3*3*3*3*3*4*4*4*4*5*5*6*7)$
$d_8 = 6!*5!*4!*4!*3!*3!*3!**2!*2!*2*2*2*2!*2*2*2!*2!*2*2*2 / (3*3*3*3*3*3*3*3*4*4*4*4*4*4*4*5*5*5*6*6*7*8)$

Zapewne pomylilem sie gdzies po drodze, ale wyglada jak kolejne wykładniki Fibonacciego, wiec strzelam, ze:

$d_n = \displaystyle \prod_{i=0}^{n-2}{ (n-2-i)!^{F(i)} } \cdot \prod_{i=0}^{n-1}{ \frac{1}{(n-i)!^{F(i)}} }$

$n = 2$. $d_2 = 1.$ OK

$n > 2$. $\displaystyle d_n = \frac{(n-2)!}{n} \cdot d_{n-1} \cdot d_{n-2} = \frac{(n-2)!}{n} \prod_{i=0}^{n-4}{ (n-4-i)!^{F(i)} } \cdot \prod_{i=0}^{n-3}{ (n-3-i)!^{F(i)} } \cdot \prod_{i=0}^{n-3}{ \frac{1}{(n-2-i)!^{F(i)}} } \cdot \prod_{i=0}^{n-2}{ \frac{1}{(n-1-i)!^{F(i)}} } =$ ciag dalszy byc moze nastapi


Inne rozwiązanie:
 $d_0 = 1$ , $d_1 = 2$

 $n \cdot d_n = (n-2)!d_{n-1}d_{n-2} $

 Pomnóżmy równość przez $(n-1)!$

 $n!d_n = (n-1)!d_{n-1}\cdot (n-2)!d_{n-2}$

 Stwórzmy nowy ciąg: 

 $a_n = n!d_n$

 mamy, więc

 $a_n = a_{n-1}a_{n-2} $ co rozwiązaliśmy w zadaniu 4. c), zatem:

 $2^{F_n} = a_n = n!d_n$

 $d_n = \frac{2^F_n}{n!} $

===== Zadanie 8. =====
===== Zadanie 9. =====
===== Zadanie 10. =====
===== Zadanie 11. =====
===== Zadanie 12. =====
===== Zadanie 13. =====
===== Zadanie 14. =====
===== Zadanie 15. =====
{{tag>[listy_zadan]}}