Indukcja i Rekurencja

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Sebastiusz
Witam na forum
Witam na forum
Posty: 3
Rejestracja: 28 lis 2018, 20:13
Podziękowania: 5 razy

Indukcja i Rekurencja

Post autor: Sebastiusz » 28 lis 2018, 20:41

Zadanie 1 .

Powołując się na indukcje matematyczną pokazać, że jeśli funkcja f : N \(\to\) N spełnia warunek :


\(\begin{cases}f (0) = 2\\ f(n) =4f(n-1)-3, n \ge 1. \end{cases}\)

to \({f(n)=4^n + 1 }, \ge 0.\)

zadanie 2.

Niech funkcja f : N \(\to\) n spełnia warunek :

\(\begin{cases}f (0) = 6\\ f(n) =f(n-1)+12n+6, n \ge 1. \end{cases}\)

Wykorzystując rekurencje, obliczyć wartość funkcji f(n) dla n = 5,6,7,8,9,10

Dziękuje za pomoc :)

radagast
Guru
Guru
Posty: 16726
Rejestracja: 09 lis 2010, 08:38
Lokalizacja: Warszawa
Podziękowania: 25 razy
Otrzymane podziękowania: 7062 razy
Płeć:

Re: Indukcja i Rekurencja

Post autor: radagast » 29 lis 2018, 17:04

Sebastiusz pisze:Zadanie 1 .

Powołując się na indukcje matematyczną pokazać, że jeśli funkcja f : N \(\to\) N spełnia warunek :


\(\begin{cases}f (0) = 2\\ f(n) =4f(n-1)-3, n \ge 1. \end{cases}\)

to \({f(n)=4^n + 1 }, \ge 0.\)
1) Twierdzenie jest prawdziwe dla n=0
2) zał ind :\(\exists n \in N:\ \ f(n-1)=4^{n-1} + 1\)
teza:\(f(n)=4^{n} + 1\)
dowód:
\(f(n)=4f(n-1)-3=^{z\ zał\ ind}=4 \left(4^{n-1} + 1 \right)-3=4^{n} + 1\)
CBDO