Zadna z osob, ktore pytalem do tej pory nie potrafila mi pomoc. Moglby jakis geniusz pomoc w rozwiazaniu tych zadan? To ostatnia deska ratunku dla tonacego. Bede wdzieczny za kazda pomoc, Dziekuje.
\(\displaystyle{ Zadanie\ 1.
a)}\)
Dla ciągu:
\(\displaystyle{ \begin{cases}F(n) = F_{n-1} + F_{n-2}\ \ \ \ \ n>=2\\F_0 = 0,\ F_1 = 1 \end{cases}}\)
udowodnij indukcyjnie następującą zależność:
\(\displaystyle{ P(n):\ F_{n+1} F_{n-1} - {F_{n}}^2 = (-1)^n\ \ \ \ \ n>=1}\)
\(\displaystyle{ b)
1^2-2^2+3^2+...+(-1)^{n+1}n^2 = (-1)^{n+1}(1+2+...+n)}\)
\(\displaystyle{ Zadanie\ 2.
a)}\)
Udowodnij poprawność następującego algorytmu:
\(\displaystyle{ Precondition\ \left { input:\ nieujemna\ liczba\ n \in N\right}
Algorytm\ \left{ oblicza\ \frac{1}{3} \ iloczynu\ kolejnych\ 3\ liczb\ naturalnych\ poczawszy\ od\ n \right}
mult:=0
k:=0
\ \ \ \ \ \ \ \ \ \ loop\ invanant\ \left{ mult= \frac{1}{3} \left( k \left( k+1 \right) \left( k+2 \right) \right) \right}
\ \ \ \ \ \ \ \ \ \ while \ \ \ k<n \ \ \ do
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k:=1
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ mult:=mult + k \left(k+1 \right)
\ \ \ \ \ \ \ \ \ \ end\ while
Postcondition\ \left { output:\ mult= \left( \frac{1}{3} \right)n \left(n+1 \right) \left(n+2 \right) \right}}\)
\(\displaystyle{ b)}\)
Udowodnij przez indukcję:
\(\displaystyle{ P(n):\ (2^{n+2}+3^{2n+1} : 7\ \ \ \ \ n>=1}\)
\(\displaystyle{ c)}\)
Rozwiąż równania różnicowe:
\(\displaystyle{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a_n + 4a_{n-1} + 4a_{n-2} = f(n)\ \ \ \ \ n>=2
(i) \ \ \ f(n) = 5 * (-2)^n\ \ \ \ \ \ \ \ \ \ ii)\ \ \ f(n) = 3^n
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a_0 = 1\ \ \ a_1 = 1}\)
\(\displaystyle{ Zadanie\ 3.}\)
Używając funkcji generujących znajdź rozwiązanie schematu rekurencyjnego:
\(\displaystyle{ a_{n+2} - 5a_{n+1} + 6a_n = 2\ \ \ \ \ n>=0
\ \ \ \ \ \ a_0 = 3\ \ \ a_1 = 7}\)
Uwaga! Skorzystaj z równości:
\(\displaystyle{ \frac{10x^2-11x+3}{(1-x)(1-2x)(1-3x)} = \frac{2}{1-3x} + \frac{1}{1-x}}\)
\(\displaystyle{ Zadanie\ 4.
a)}\)
Znajdź postać jawną (z dowodem) dla ciągu:
\(\displaystyle{ T(n) = 8 T( podloga( \frac{n}{2}) )
T(1) = 4
podloga\ =\ calkowite\ zaokraglenie\ w\ dol\ np.\ podloga(\frac{1}{2})=0
Okresl\ asymptotyke\ T(n) = O(?)}\)
\(\displaystyle{ b)}\)
Dla ciągu:
\(\displaystyle{ S_n = \sum_{n}^{k=1} \frac{n^2}{(2k-1)(2k+1)}}\)
Określ:
\(\displaystyle{ S_n = \Theta (?)}\)
Bardzo dziekuję za jakąkolwiek pomoc.
Indukcja, rownania roznicowe, postac jawna - 4 zadania
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Indukcja, rownania roznicowe, postac jawna - 4 zadania
1 a)
Oznaczmy:
\(\displaystyle{ G_n=F_{n+1}F_{n-1}-F_n^2}\).
Wówczas dla \(\displaystyle{ n>2}\):
\(\displaystyle{ G_n=F_{n+1}F_{n-1}-F_n^2=(F_n+F_{n-1})F_{n-1}-(F_{n-1}+F_{n-2})F_n=}\)
\(\displaystyle{ =-(F_nF_{n-2}-F_{n-1}^2)=-G_{n-1}}\).
Skąd trywialnie przez indukcję:
\(\displaystyle{ G_n=(-1)^{n-1}G_1=(-1)^n}\)
i w związku z tym teza zadania.
1 b)
Lewa strona \(\displaystyle{ L(n)}\), prawa strona \(\displaystyle{ P(n)}\). Sprawdzamy, że:
\(\displaystyle{ 1=L(1)=P(1)}\).
Krok indukcyjny natomiast wnioskujemy z:
\(\displaystyle{ L(n+1)-L(n)=(-1)^{n+2}(n+1)^2}\)
\(\displaystyle{ P(n+1)-P(n)=(-1)^{n+2}\sum_{i=1}^{n+1}i+(-1)^{n+2}\sum_{i=1}^ni=(-1)^{n+2}\cdot(2\cdot\sum_{i=1}^ni+n+1)=}\)
\(\displaystyle{ =(-1)^{n+2}\cdot\left(2\cdot \frac{n(n+1)}{2}+n+1\right)=(-1)^{n+2}(n+1)^2}\)
2 b)
Krok indukcyjny:
\(\displaystyle{ P(n)=2^{n+2}+3^{2n+1}=2\cdot 2^{n+1}+9\cdot 3^{2(n-1)+1}=}\)
\(\displaystyle{ =2(2^{n+1}+3^{2(n-1)+1})+7\cdot 3^{2(n-1)+1}=2P(n-1)+7\cdot 3^{2(n-1)+1}}\)
jeśli więc \(\displaystyle{ 7|P(n-1)}\), to również \(\displaystyle{ 7|P(n)}\), co zamyka krok indukcyjny.
3.
Funkcja tworząca tego ciągu na odpowiednim przedziale spełnia równanie:
\(\displaystyle{ f(x)-a_1x-a_0-5x(f(x)-a_0)+6x^2f(x)=\frac{2x^2}{1-x}}\)
czyli równanie:
\(\displaystyle{ f(x)+8x-3-5xf(x)+6x^2f(x)=\frac{2x^2}{1-x}}\)
skąd:
\(\displaystyle{ f(x)(1-5x+6x^2)=\frac{(3-8x)(1-x)+2x^2}{1-x}}\)
i ostatecznie:
\(\displaystyle{ f(x)=\frac{(3-8x)(1-x)+2x^2}{(1-x)(1-5x+6x^2)}=\frac{10x^2-11x+3}{(x-1)(2x-1)(3x-1)}}\)
Korzystając ze wskazówki otrzymujemy więc:
\(\displaystyle{ f(x)=\frac{2}{1-3x}+\frac 1{1-x}=\sum_{n=0}^\infty 2\cdot 3^n\cdot x^n+\sum_{n=0}^\infty x^n}\)
i, co za tym idzie, \(\displaystyle{ a_n=2\cdot 3^n+1}\).
4 a)
O ile udało mi się napisy odczytać zgodnie z intencją autora wątku:
Nietrudno zauważyć, że jeśli liczba \(\displaystyle{ n}\) ma \(\displaystyle{ k}\) cyfr w zapisie dwójkowym, to:
\(\displaystyle{ T(n)=4\cdot 8^{k-1}}\)
bo
\(\displaystyle{ \left\lfloor\frac n2\right\rfloor}\)
ma o jedną cyfrę mniej w zapisie.
Skąd
\(\displaystyle{ T(n)=4\cdot 8^{\lfloor\log_2 n\rfloor}}\),
co daje:
\(\displaystyle{ T(n)\in\mathcal{O}(n^3)}\).
4 b)
Najprościej jest zauważyć, że szereg \(\displaystyle{ \sum_{k=1}^\infty\frac 1{(2k+1)(2k-1)}}\) jest zbieżny bazwzględnie - wystarczy porównać z szeregiem \(\displaystyle{ \sum\frac{1}{n^2}}\) - i wobec tego \(\displaystyle{ S_n\in\Theta(n^2)}\).
Alternatywnie można wyznaczyć \(\displaystyle{ S_n}\):
\(\displaystyle{ S_n=n^2\sum_{k=1}^n\frac 1{(2k-1)(2k+1)}=n^2\sum_{k=1}^n\frac 12\cdot\left(\frac{1}{2k-1}-\frac{1}{2k+1}\right)=}\)
\(\displaystyle{ =\frac{n^2}2\cdot\left(1+\frac 13-\frac 1{2n-1}-\frac 1{2n+1}\right)=\frac{2n^2}3-\frac{n^2}{4n-2}-\frac{n^2}{4n+2}\in\Theta(n^2)}\)
Oznaczmy:
\(\displaystyle{ G_n=F_{n+1}F_{n-1}-F_n^2}\).
Wówczas dla \(\displaystyle{ n>2}\):
\(\displaystyle{ G_n=F_{n+1}F_{n-1}-F_n^2=(F_n+F_{n-1})F_{n-1}-(F_{n-1}+F_{n-2})F_n=}\)
\(\displaystyle{ =-(F_nF_{n-2}-F_{n-1}^2)=-G_{n-1}}\).
Skąd trywialnie przez indukcję:
\(\displaystyle{ G_n=(-1)^{n-1}G_1=(-1)^n}\)
i w związku z tym teza zadania.
1 b)
Lewa strona \(\displaystyle{ L(n)}\), prawa strona \(\displaystyle{ P(n)}\). Sprawdzamy, że:
\(\displaystyle{ 1=L(1)=P(1)}\).
Krok indukcyjny natomiast wnioskujemy z:
\(\displaystyle{ L(n+1)-L(n)=(-1)^{n+2}(n+1)^2}\)
\(\displaystyle{ P(n+1)-P(n)=(-1)^{n+2}\sum_{i=1}^{n+1}i+(-1)^{n+2}\sum_{i=1}^ni=(-1)^{n+2}\cdot(2\cdot\sum_{i=1}^ni+n+1)=}\)
\(\displaystyle{ =(-1)^{n+2}\cdot\left(2\cdot \frac{n(n+1)}{2}+n+1\right)=(-1)^{n+2}(n+1)^2}\)
2 b)
Krok indukcyjny:
\(\displaystyle{ P(n)=2^{n+2}+3^{2n+1}=2\cdot 2^{n+1}+9\cdot 3^{2(n-1)+1}=}\)
\(\displaystyle{ =2(2^{n+1}+3^{2(n-1)+1})+7\cdot 3^{2(n-1)+1}=2P(n-1)+7\cdot 3^{2(n-1)+1}}\)
jeśli więc \(\displaystyle{ 7|P(n-1)}\), to również \(\displaystyle{ 7|P(n)}\), co zamyka krok indukcyjny.
3.
Funkcja tworząca tego ciągu na odpowiednim przedziale spełnia równanie:
\(\displaystyle{ f(x)-a_1x-a_0-5x(f(x)-a_0)+6x^2f(x)=\frac{2x^2}{1-x}}\)
czyli równanie:
\(\displaystyle{ f(x)+8x-3-5xf(x)+6x^2f(x)=\frac{2x^2}{1-x}}\)
skąd:
\(\displaystyle{ f(x)(1-5x+6x^2)=\frac{(3-8x)(1-x)+2x^2}{1-x}}\)
i ostatecznie:
\(\displaystyle{ f(x)=\frac{(3-8x)(1-x)+2x^2}{(1-x)(1-5x+6x^2)}=\frac{10x^2-11x+3}{(x-1)(2x-1)(3x-1)}}\)
Korzystając ze wskazówki otrzymujemy więc:
\(\displaystyle{ f(x)=\frac{2}{1-3x}+\frac 1{1-x}=\sum_{n=0}^\infty 2\cdot 3^n\cdot x^n+\sum_{n=0}^\infty x^n}\)
i, co za tym idzie, \(\displaystyle{ a_n=2\cdot 3^n+1}\).
4 a)
O ile udało mi się napisy odczytać zgodnie z intencją autora wątku:
Nietrudno zauważyć, że jeśli liczba \(\displaystyle{ n}\) ma \(\displaystyle{ k}\) cyfr w zapisie dwójkowym, to:
\(\displaystyle{ T(n)=4\cdot 8^{k-1}}\)
bo
\(\displaystyle{ \left\lfloor\frac n2\right\rfloor}\)
ma o jedną cyfrę mniej w zapisie.
Skąd
\(\displaystyle{ T(n)=4\cdot 8^{\lfloor\log_2 n\rfloor}}\),
co daje:
\(\displaystyle{ T(n)\in\mathcal{O}(n^3)}\).
4 b)
Najprościej jest zauważyć, że szereg \(\displaystyle{ \sum_{k=1}^\infty\frac 1{(2k+1)(2k-1)}}\) jest zbieżny bazwzględnie - wystarczy porównać z szeregiem \(\displaystyle{ \sum\frac{1}{n^2}}\) - i wobec tego \(\displaystyle{ S_n\in\Theta(n^2)}\).
Alternatywnie można wyznaczyć \(\displaystyle{ S_n}\):
\(\displaystyle{ S_n=n^2\sum_{k=1}^n\frac 1{(2k-1)(2k+1)}=n^2\sum_{k=1}^n\frac 12\cdot\left(\frac{1}{2k-1}-\frac{1}{2k+1}\right)=}\)
\(\displaystyle{ =\frac{n^2}2\cdot\left(1+\frac 13-\frac 1{2n-1}-\frac 1{2n+1}\right)=\frac{2n^2}3-\frac{n^2}{4n-2}-\frac{n^2}{4n+2}\in\Theta(n^2)}\)