n 500 8% n 0 , 1 0 50 n 6% n =9 ,k =3 n k n − k n n 5 9.7Esercizi W ( X ) H ( X ) W ( X ) H ( X ) ( R ) c W ( X ) H ( X ) 1 c c + c X + ... + c X W ( X ) H ( X )= . 1 h X

(1)

e dunque

1 c0

W (X)H(X) =

�∞ n=r

hnXⁿ

c0+ c1X + ... + crX^r. Sempre per la Proposizione 9.70 si riconosce che 1

c0

W (X)H(X)`e la OGF di una soluzione della relazione(R). La conclusione segue dal fatto che la successione dei coefficienti diW (X)H(X) `e la convoluzione delle successioni dei coefficienti di W (X)eH(X).

9.7 Esercizi

Esercizio 9.1 Si trovi una relazione di ricorrenza per il numero di possibili di- stribuzioni di n oggetti distinti in 5 ripiani di una armadio. Qual `e la condizione iniziale?

Esercizio 9.2 Si trovi una relazione di ricorrenza per il numero di sequenze di macchine di tipo Cadillac, Continental, Ford in una fila di nposti macchina, tenendo presente che una Cadillac o una Continental necessitano di due posti macchina per il parcheggio, mentre una Ford ne richiede uno solo.

Esercizio 9.3 Supponiamo che ogni coppia di lepri generi ogni mese una nuova coppia (un maschio ed una femmina) di lepri. Trovare la relazione di ricorrenza che descrive il numero di coppie di lepri mese dopo mese. Se inizialmente c’`e una sola coppia di lepri appena nate, qual `e il numero di coppie di lepri dopo 5 mesi.

Esercizio 9.4 (a) Si trovi una relazione di ricorrenza per il numero di regioni create danrette nel piano sekdi queste rette sono parallele e le altren− kintersecano tutte le altre con la condizione che tre rette non passino per uno stesso punto;

(b) sen = 9, k = 3si trovi il numero di regioni.

Esercizio 9.5 Si trovi una relazione di ricorrenza per l’ammontare del denaro depo- sitato in un conto bancario dopo nanni se l’interesse `e del6%ed ogni anno sono aggiunti al conto50euro.

Esercizio 9.6 Si trovi una relazione di ricorrenza per contare il numero di sequenze dincifre dove compaiano solo0, 1con almeno un caso di cifre0consecutive.

Esercizio 9.7 Se 500 euro vengono investiti in un fondo che d`a l’8% di interessi all’anno, trovare una formula per calcolare la quantit`a di denaro accumulato dopon anni.

(2)

Esercizio 9.8 Dimostrare che la successione(an)n≥1definita ponendo

an =

�1 sen = 2^m,

2� + 1 sen = 2^m+ �, 1≤ � < 2^m

`e una soluzione della relazione di ricorrenza

xn =

�2xn/2− 1 sen≥ 2^{`e pari}, 2x(n−1)/2+ 1 sen≥ 3^{`e dispari} con dato inizialex1= 1.

Esercizio 9.9 Risolvere le seguenti relazioni di ricorrenza:

(a) xn = 3xn−1+ 4xn−2con condizioni inizialix0= x1 = 1; (b) xn = xn−2con condizioni inizialix0 = x1 = 1;

(c) xn = 2xn−1− xⁿ−2con condizioni inizialix0 = x1 = 2;

(d) xn = 3xn−1− 3xⁿ−2+ xn−3con condizioni inizialix0 = x1= 1, x2= 2. Esercizio 9.10 Trovare e risolvere una relazione di ricorrenza che calcoli i possibili modi per riempire un una fila dinposti di un parcheggio utilizzando macchine blu e rosse e camion, tenendo conto che i camion occupano due spazi, le macchine ne occupano uno.

Esercizio 9.11 Una multinazionale farmaceutica decide di raddoppiare ogni anno l’aumento di prezzo del suo prodotto di punta. Trovare e risolvere la relazione di ricorrenza per il prezzopndel prodotto nell’annon, supponendo chep0= 1, p1= 4. Esercizio 9.12 La relazione di ricorrenza xn = c1x_n−1 + c2x_n−2 ha soluzione generalexn = A13ⁿ+ A26ⁿ: determinarec1, c2.

Esercizio 9.13 Sia h una funzione definita su N e c una costante. Determinare, procedendo a ritroso, la soluzione dixn= cx_n−1+ h(n)conx0= 1.

Esercizio 9.14 Si risolvano le seguenti relazioni di ricorrenza:

(a) xn = xn−1+ 3(n− 1)^,x0= 1; (b) xn = xn−1+ n(n− 1)^,x0= 3; (c) xn = x_n−1+ 3n²,x0= 10.

Esercizio 9.15 (a) Si trovi e si risolva una relazione di ricorrenza per il numero di sottoscacchiere quadrate di misura qualsiasi che possono essere disegnate su una scacchieran× n^.

(b) Si ripeta la parte(a)per sottoscacchiere rettangolari di qualunque tipo.

(3)

Esercizio 9.16 Se il polinomio caratteristico di una certa relazione di ricorrenza è (X− 1)²(X− 2)(X − 3)², si determini la soluzione generale della sua parte omo- genea. Si determini di che tipo può essere una soluzione particolare delle relazione quando la sua parte non omogeneah è definita da:

(a) h(n) = 4n³+ 5n; (b) h(n) = 4ⁿ; (c) h(n) = 3ⁿ.

Esercizio 9.17 Risolvere le seguenti relazioni di ricorrenza:

(a) xn = 3xn−1− 2^,x0 = 0; (b) xn = 2x_n−1+ (−1)ⁿ^,x0= 2; (c) xn = 2xn−1+ n,x0= 1; (d) xn = 2xn−1+ 2n²,x0= 3.

Esercizio 9.18 Si risolva la relazione di ricorrenzaxn = 3x_n−1− 2xn−2+ 3,x0 = x1 = 1.

Esercizio 9.19 Trovare e risolvere una relazione di ricorrenza per il guadagno di un’azienda, se il tasso di crescita del guadagno nell’annok-esimo rispetto all’anno precedente `e di10(2^k)euro, con sequenza di condizioni iniziali(29, 1 020).

Esercizio 9.20 Si determini una soluzione particolare della relazionexn = cx_n−1+ h(n)con

(a) h(n) = 1; (b) h(n) = n; (c) h(n) = n²; (d) h(n) = qⁿ.

Esercizio 9.21 Si trovi la soluzione generale perxn− 5xn−1+ 6x_n−2= 2 + 3n. Esercizio 9.22 Si risolvano le seguenti relazioni di ricorrenza con condizione iniziale x0 = 1:

(a) y²_n = 2y_n²₋₁+ 1(suggerimento: porrexn = y²_n);

(b) yn = −nyn−1+ n!(suggerimento: definire un opportunoxn come nella parte (a)).

Esercizio 9.23 Determinare la soluzione generale della relazione xn = 4x_n−1 − 4xn−2+ 2ⁿ.

Esercizio 9.24 Si risolvaxn = xn−1+ 12n², conx0= 5.

(4)

Esercizio 9.25 Determinare la soluzione generale della relazione xn = 3xn−1 − 4n + 3(2ⁿ). Risolvere poi la relazione con dato inizialex1 = 8.

Esercizio 9.26 Determinare una soluzione particolare di ciascuna delle seguenti ricorrenze:

1. xn+1= 5xn+ 2ⁿcos^�nπ 3

�;

2. xn+1= 5xn+ 2ⁿn cos^�nπ 3

�.

Determinarne poi la soluzione conx0 = 0.

Esercizio 9.27 Determinare una soluzione particolare della ricorrenza:

xn+2− 4√

3xn+1+ 16xn = 5× 4ⁿcos^�cos^�nπ 6

��

. Determinare poi la soluzione conx0 = 0, x1= 1.

Esercizio 9.28 Determinare la soluzione generale della ricorrenza:

xn+1= xn+ (1 + n)2ⁿcos^�sin^�nπ 3

��.

Determinare poi la soluzione conx0 = 1.

Esercizio 9.29 Determinare la soluzione delle seguenti relazioni “dividi e conquista”:

(a) xn = 2xn/2+ 5con dato inizialex1= 1; (b) xn = 2xn/4+ ncon dato inizialex1= 3; (c) xn = 2xn/2+ 2ncon dato inizialex1= 5; (d) xn = an/3+ 4con dato inizialex1= 7.

Esercizio 9.30 Determinare le soluzione delle relazioni “dividi e conquista”

(a) xn = xn/3+ 2con condizione inizialex4= 5; (b) xn = 2xn/3+ 2con condizione inizialex1= 1. (c) xn = xn/3+ 2ncon condizione inizialex1 = 5; (d) xn = 2xn/3+ 2ncon condizione inizialex2=−1^.

Esercizio 9.31 Descrivere un approccio del tipo “dividi e conquista” per determinare il massimo tra gli elementi di un insieme dinnumeri. Scrivere una relazione di ricorrenza sul numero di confronti necessari e risolverla.

Esercizio 9.32 Descrivere un approccio del tipo “dividi e conquista” per determinare il primo ed il secondo per grandezza tra gli elementi di un insieme dinnumeri distinti.

Scrivere una relazione di ricorrenza sul numero di confronti necessari e risolverla.

(5)

Esercizio 9.33 Determinare una stima dell’ordine di grandezza (cio`ean = O(...)) per la soluzione(an)ndella relazione “dividi e conquista”

xn = 3xn/2+ 4n² n = 2^k, k∈N

con condizione iniziale x1 = 5; risolverla poi esplicitamente e verificare quanto trovato sopra.

xn= 2xn/2+ 2, n = 2^k, k∈N

xn = 2xn/2+ 2 log₂n, n = 2^k, k∈N

xn = 4xn/4+ 3 log₄n, n = 4^k, k∈N

Esercizio 9.37 Utilizzando le funzioni generatrici risolvere la ricorrenza xn = 11xn−2− 6xⁿ−3 n > 2 x0= 0, x1= x2= 1.

Esercizio 9.38 Utilizzando le funzioni generatrici risolvere la ricorrenza xn= 3x_n−1− 3xn−2+ x_n−3 n > 2 x0= x1= 0 x2= 1.

Risolvere la ricorrenza data sopra con le condizioni inizialix0 = 0,x1 = x2= 1. Esercizio 9.39 Utilizzando le funzioni generatrici risolvere le ricorrenze

xn = 5x_n−1− 8xn−2+ 4x_n−3 n > 2 x0 = 1, x1 = 2, x2 = 4;

xn= 2xn−2− xⁿ−4 n > 4 x0= x1= 0, x2= x3= 1;

xn = 6x_n−1− 12xn−2+ 18x_n−3− 27xn−4n > 4 x0 = 0, x1 = x2= x3= 1.

(6)

Esercizio 9.40 Utilizzando le funzioni generatrici risolvere la ricorrenza

xn =

�m k=1

�m k

�

xn−m n≥ m x⁰= ... = xm−2 = 0, xm−1 = 1

Esercizio 9.41 Utilizzando le funzioni generatrici, risolvere le seguenti relazioni di ricorrenza:

1. xn =−xⁿ−1+ 6xn−2 n > 1 x0= 0, x1= 1;

2. xn = 3xn−1− 4xⁿ−2 n > 1 x0= 0, x1= 1;

3. xn = xn−1− xⁿ−2 n > 1 x0= 0, x1 = 1.

Esercizio 9.42 Utilizzare le OGF per risolvere la ricorrenza nxn= (n− 2)xn−1+ 2 n > 2 x1= 1.

Esercizio 9.43 Utilizzare le OGF per risolvere la ricorrenza

(n + 1)xn+1= (n + 100)xn n > 0 x0= 1.

Esercizio 9.44 (∗) Utilizzare le OGF per risolvere la ricorrenza

xn = n + 1 + t n

�n k=1

xk−1 n≥ 1 x⁰= 0

nei casi in cuit = 2− ε^et = 2 + ε, conεcostante positiva sufficientemente piccola.

Soluzioni degli esercizi Soluzione es. 9.1.

Soluzione es. 9.2.

Soluzione es. 9.3.

Soluzione es. 9.4.

Soluzione es. 9.5.

Soluzione es. 9.6.

Soluzione es. 9.7.

(7)

Soluzione es. 9.8. Ogni naturalen≥ 1si scrive nella forman = 2^m+ �con0≤ � <

2^mem ≥ 0. Intanto, essendoa1 = 1, la successione(an)n verifica la condizione iniziale. Sia oran > 1; si han = 2^m+ �con0≤ � < 2^mem≥ 1. Se� = 0si ha

a2^m = 1 = 2 ˙1− 1 = 2a²^m⁻¹− 1 e quindi `e verificata la relazione di ricorrenza. Sia ora�≥ 1.

Se� = 2kcon1≤ � < 2^m, allora si ha1≤ k < 2^m−1e quindi essendo a2^m+� = 2� + 1 = 2· 2k + 1 = 2 · (2k + 1) − 1 = 2 · a2^m⁻¹+k− 1 la relazione di ricorrenza `e verificata.

Se� = 2k + 1con1≤ � < 2^m, allora si ha0≤ k < 2^m⁻¹e quindi essendo a2^m+�= 2� + 1 = 2· (2k + 1) + 1 = 2 · a²^m⁻¹^+k+ 1 la relazione di ricorrenza `e verificata.

Soluzione es. 9.9.

Soluzione es. 9.10.

Soluzione es. 9.11.

Soluzione es. 9.12.

Soluzione es. 9.13.

Soluzione es. 9.14.

Soluzione es. 9.15.

Soluzione es. 9.16.

Soluzione es. 9.17.

Soluzione es. 9.18.

Soluzione es. 9.19.

Soluzione es. 9.20.

Soluzione es. 9.21.

Soluzione es. 9.22.

Soluzione es. 9.23.

(8)

Soluzione es. 9.24.

Soluzione es. 9.25.

Soluzione es. 9.26.

Soluzione es. 9.27.

Soluzione es. 9.28.

Soluzione es. 9.29. (a)xn = 6n− 5, (b)xn=√

n + 2n, (c)xn = 5n + 2n log₂n, (d)xn = 7 + 4 log₃n.

Soluzione es. 9.30. (a)xn= 5+2 log₃(n/4), (b)xn = 3n^log³²−2^{, (c)}xn= 2+3n, (d)xn =−13(n/2)^log³²+ 6n.

Soluzione es. 9.31.

Soluzione es. 9.32.

Soluzione es. 9.33.

Soluzione es. 9.34.

Soluzione es. 9.35.

Soluzione es. 9.36.

Soluzione es. 9.37.

Soluzione es. 9.38.

Soluzione es. 9.39.

Soluzione es. 9.40.

Soluzione es. 9.41.

Soluzione es. 9.42.

Soluzione es. 9.43.

Soluzione es. 9.44.