Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 4, 17.-19.10.

1. Portaikossa voi nousta 1 tai 2 askelmaa kerrallaan. Laadi rekursioyhtälö, joka kuvaa montako erilaista tapaa on nousta ylös $n$-askelmainen portaikko. (Ohje: Osita $n$-askelmaisen portaikon nousutavat sen mukaan, noustaanko 1. askelella 1 vai 2 askelmaa.)

2. Ratkaise seuraavat rekursioyhtälöt karakterististen polynomien tekniikalla:
   1. 
      
      $$\left\{\begin{array}{l} t_0 = 0, \quad t_1 = 1,\\ t_n = 5t_{n-1} - 6t_{n-2}, \quad n \geq 2; \end{array}\right.$$
      
      

   2. 
      
      $$\left\{\begin{array}{l} a_0 = 1,\\ a_n = 2a_{n-1} + n, \quad n \geq 1. \end{array}\right.$$
      
      

3. Olkoon $A(x)$ lukujonon $\langle a_k \rangle = \langle a_0, a_1, a_2, \dots \rangle$ generoiva funktio ja $c \in {\mathbf R}$, $p \in {\mathbf N}$ vakioita. Minkä lukujonojen generoivia funktioita ovat seuraavat:
   1. $G(x) = A(cx)$,
   2. $H(x) = A(x^p)$,
   3. $A_0(x) = \frac{1}{2}(A(x) + A(-x))$ ja $A_1(x) = \frac{1}{2}(A(x) - A(-x))$?

4. Muodosta seuraavien lukujonojen generoivat funktiot:
   1. $\langle 0,0,0,0,-6,6,-6,6,-6,\dots \rangle$;
   2. $\langle 1,0,1,0,1,0,\dots \rangle$;
   3. $\langle 1,2,1,4,1,8,\dots \rangle$;
   4. $\langle 1,1,0,1,1,0,1,1,0,\dots \rangle$.

5. Newtonin (yleistetyn) binomikaavan mukaan on kaikilla $r \in {\mathbf R}$ ja $\vert x\vert < 1$ voimassa:
   
   $$(1+x)^r = \sum_{k \geq 0} {{r}\choose{k}} x^k,$$
   
   
   missä yleistetty binomikerroin ${{r}\choose{k}}$ määritellään:
   
   $${{r}\choose{k}} = \frac{r(r-1)\cdots(r-k+1)}{k!}, \qquad r \in {\mathbf R},\; k \in {\mathbf N}.$$
   
   
   Lisäksi määritellään ${{r}\choose{k}} = 0$, kun $k < 0$. Todista seuraavat yleistettyjen binomikertoimien ominaisuudet:
   1. ${{n}\choose{k}} = 0$, kun $n \in {\mathbf N}$ ja $k > n$;
   2. ${{-n}\choose{k}} = (-1)^k{{n+k-1}\choose{k}}$, kun $n \in {\mathbf N}$;
   3. ${{-1/2}\choose{k}} = \frac{(-1)^k}{2^{2k}}{{2k}\choose{k}}$, ${{1/2}\choose{k}} = \frac{(-1)^{k-1}}{2^{2k}(2k-1)}{{2k}\choose{k}}$.

6. Minkä lukujonojen generoivia funktioita ovat $\frac{1}{(1-x)^2}$ ja $\frac{x}{(1-x)^2}$? (Vihje: Sovella edellisen tehtävän tuloksia.)

7. Ratkaise tehtävän 2(b) rekursioyhtälö generoivien funktioiden avulla.