Indukcja i Rekurencja

[Sebastiusz]

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]

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