Si consideri la funzione $f: \mathbb{N} \rightarrow \mathbb{N}$ definita nel seguente modo:
$$
f(0)=1, \quad f(1)=3, \quad f(n)=6 f(n-2)+f(n-1) \text { per } n>1 .
$$
Determinare le immagini dei primi 5 numeri naturali e dimostrare per induzione forte su $n$ che $f(n)=3^n$.
Qualcuno sa dimostrarmi l’induzione forte in questo es?
127
punti
Livello 1
Per economia di calcolo io invertirei le consegne.
---------------
Dalla definizione ricorsiva
* (f(n) = 6*f(n - 2) + f(n - 1)) & (n > 1)
e dall'innesco della successione
* (f(0) = 1 = 3^0) & (f(1) = 3 = 3^1)
si verifica il passo base
* f(2) = 6*f(0) + f(1) = 6 + 3 = 3^2
poi si dimostra per sostituzione che, nell'ipotesi di f(k) = 3^k per ogni k <= n,
* f(n + 1) = 6*f(n - 1) + f(n) =
= 6*3^(n - 1) + 3^n =
= 6*3^n/3 + 3^n =
= (6/3 + 1)*3^n = 3*3^n = 3^(n + 1)
QED
---------------
Per le immagini dei primi cinque numeri naturali vedi le coppie {k, f(k)} al link
http://www.wolframalpha.com/input?i=table%5B%7Bk%2C3%5Ek%7D%2C%7Bk%2C1%2C11%7D%5D
però se ti va te le puoi calcolare ricorsivamente da te.
---------------
AVVERTENZA
La forma chiusa "f(n) = 3^n" vale solo per questo particolare innesco, ma in generale
* (f(0) = a) & (f(1) = b) & (f(n) = 6*f(n - 2) + f(n - 1)) & (n > 1) ≡
≡ f(n) = ((2*a + b)*3^n + (3*a - b)*(- 2)^n)/5
51246
punti
Genius I
@exprof ...great job !!!👍👍👍
