Polsl-Notes/AiSD/Ćwiczenia/1. Rozwiązywanie równań rekurencyjnych.md

Date

Date
20230310110354

Problem Rekurencyjny - Wieża Hanoi

n	T(n)
1	1
2	3
3	7
4	15
...	...
10	1023

T(n)=\begin{cases}0\ dla\ n=0\\2\cdot T_{n-1} + 1\ dla\ n>0 \\ \end{cases} T_{n+1}=2^{n+1}-1 L=T_{n+1}=2\cdot T_{n}+1=2\cdot(2^{n}-1)+1=2^{n+1}-2+1=2^{n+1}-1=P

Sumy

Notacja

S_{n}=a_{1}+a_{2}+\dots+a_{n}=\sum\limits_{k=1}^{n}a_{k}=\sum\limits_{1\leqslant k\leqslant n}a_k

Własności

$$\begin{aligned} &\sum\limits_{k\in K}ca_{k}=c\sum\limits_{k\in K}a_{k}\\ &\sum\limits_{k\in K}(a_{k}+b_{k})=\sum\limits_{k\in K}a_{k}+\sum\limits_{k\in K}b_{k}\\ &\sum\limits_{k\in K}a_{k}=\sum\limits_{p(k)\in K}a_{p(k)} \end{aligned}$$

Suma ciągu arytmetycznego

\sum\limits_{k=0}^{n}a+bk=\cfrac{a+(a+bn)}{2}(n+1)

Suma ciągu geometrycznego

\sum\limits_{0\leqslant k\leqslant n}aq^{k}=a\cfrac{1-q^{n-1}}{1-q}, q\ne 1

Sumy jako równania rekurencyjne

S_{n}=\sum\limits_{k=0}^{n}a_{k}=a_{0}+\sum\limits_{k=1}^{n}a_{k}=\begin{cases}
a_{0},\ gdy\ n=0 \\
S_{n-1}+a_{n},\ gdy\ n>0
\end{cases}

Szereg harmoniczny, n-ta liczba harmoniczna

H_{n}=\sum\limits_{k=1}^{n}\frac{1}{k}\approx\ln n+\gamma \lim_{n\rightarrow\infty}(H_{n}-\ln n)=\gamma\approx0.5772156

Problem rekurencyjny - metody

Indukcja Matematyczna

1. \exists_{n_{0}\in N} P(n_0) jest zdaniem prawdziwym
2. \forall _{n\geqslant n_{0}} prawdziwa jest implikacja P(n) \Rightarrow P(n+1)

\Downarrow

\forall _{n\geqslant n_{0}} P(n)jest zdaniem prawdziwym

$$\begin{gathered} 1+2+3+4+n=\cfrac{1+n}{2}n\

1. n_{0}=1 \Rightarrow \end{gathered}$$

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

Zmienna Pomocnicza

$$\begin{aligned} T_{n}+1&=\begin{cases} 1\ dla\ n=0\ 2\cdot(T_{n-1}+1)\ dla\ n>0 \end{cases} \ U_{n}&=T_{n}+1\ U_{n-1}&=T_{n-1}+1 \end{aligned}$$

Metoda zaburzania / perturbacji

\begin{gathered}


S_{n}=\sum\limits_{k=0}^{n}(a_{k})=a_{0}+a_{1}+\dots+a_{n}\\
\sum\limits^{n}_{k=0}a_{k}+a_{n+1}=a_{0}+a_{1}+\dots+a_{n}+a_{n+1}=a_{0}+\sum\limits^{n}_{k=0}a_{k+1}
\end{gathered}

Równania rekurencyjne jako sumy

Metoda czynnika sumacyjnego

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Zadania Domowe

S_{n}=\sum\limits_{k=0}^{n}k\cdot2^{k}