Lezione 19 (26 aprile 1999 h. 9.30-10.30)

Dimostrazione del teorema 18.11

Dim.  Supponiamo che $\alpha$ abbia molteplicità $\mu(\alpha)\ge m$ e proviamo che allora è radice di tutte le derivate fino all'ordine m-1. Procediamo per induzione su m. Se m=1 la tesi è data dal teorema di Ruffini. Supponiamo la tesi vera per m. Sia quindi $\mu(\alpha)\ge m+1$, ovvero $P=(x-\alpha)^{m+1}$ allora derivando si ottiene

$$P'=(m+1)(x-\alpha)^mQ+(x-\alpha)^{m+1}Q'=(x-\alpha)^m((m+1)Q+(x-\alpha) Q')$$

ovvero $(x-\alpha)^m\big\vert P'$ quindi $\alpha$ è radice di P' con molteplicità almeno m, per ipotesi di induzione si ha allora che $P'(\alpha)=(P')'(\alpha)=\dots (P')^{(m-1)}(\alpha)=0$, ossia $P'(\alpha)=P''(\alpha)+\dots P^{(m)}(\alpha)=0$ che insieme al fatto che $\alpha$ è radice di P dà la tesi.

Viceversa. Procediamo per induzione su m. Per m=1 la tesi è ovvia. Supponiamo la tesi vera per $m\ge1$. Sia P un polinomio e sia $\alpha$ tale che

$$P(\alpha)=P'(\alpha)=\dots P^{(m-1)}(\alpha)= P^{(m)}(\alpha)=0$$ (24)

L'ipotesi di induzione e le prime m di queste uguaglianze garantiscono che $\alpha$ è una radice di molteplicità almeno m, ossia che esiste Qtale che $P=(x-\alpha)^m Q$, da cui derivando si ottiene

$$P'=m(x-\alpha)^{m-1}Q+(x-\alpha)^mQ'=(x-\alpha)^{m-1}(mQ+(x-\alpha)Q')$$ (25)

Le ultime m uguaglianze delle (24), garantiscono invece che $\alpha$ è anche radice di P' con molteplicità almeno m ovvero che esiste R tale che $P'=(x-\alpha)^m R$. Uguagliando con la (25) si ottiene quindi

$$(x-\alpha)^m R=(x-\alpha)^{m-1}(mQ+(x-\alpha)Q')$$

da cui

$$(x-\alpha)^{m-1}(mQ+(x-\alpha)(Q'-R))=0.$$

Dato che K[x] è un dominio di integrità e $(x-\alpha)^{m-1}\ne 0$, allora $mQ+(x-\alpha)(Q'-R)$. Valutando in $\alpha$ si ottiene allora $mQ(\alpha)=0$, dato che $\mathop{\rm char}\nolimits K=0$ ciò implica che $Q(\alpha)=)$. Ma allora, per il teorema di Ruffini, $Q=(x-\alpha)S$ e quindi $P=(x-\alpha)^mQ=(x-\alpha)^m(x-\alpha)S=(x-\alpha)^{m+1}S$, che è la tesi.     $\square$

Equazioni ricorsive lineari

Sia $x\in\mathbb R^\mathbb N$ una successione, diremo che x risolve una equazione ricorsiva, se ogni elemento è funzione dei precedenti, in simboli se esistono delle funzioni $f_n:\mathbb R^{n+1}\to\mathbb R$ tali che

 

$$x_n=f_n(x_0,x_1,\dots, x_{n-1}) \quad \forall n\ge 1.$$ (26)

Supponendo di avere date le equazioni ricorsive, il problema di ricavare informazioni sulle successioni che le risolvono non è in generale di facile soluzione. Analizzeremo un caso di equazioni ricorsive di tipo particolare, per le quali si riescono a determinare esplicitamente tutte le soluzioni.

Considereremo equazioni ricorsive che hanno storia finita ovvero per le quali esiste un $k\ge1$ tale che ogni termine è funzione soltanto dei kprecedenti (i.e. le f_n hanno come dominio tutte $\mathbb R^k$) e in cui le f_nsono tutte uguali e lineari, ossia equazioni del tipo

$$x_{n+k}=\sum_{i=0}^{k-1} a_i x_{n+i} \quad \forall n\ge0$$ (27)

con $a_i\in \mathbb R$ e $a_0\ne 0$. Una tale equazione ricorsiva la chiameremo lineare a coefficienti costanti di ordine k.

Osservazione 19.1   La condizione $a_0\ne 0$ viene posta in modo che si abbia una effettiva dipendenza di ogni termine della successione dai precedenti k. Se infatti fosse a₀=0 si avrebbe che ogni termine dipenderebbe soltanto dai k-1 termini preceedenti.

Anche se nella pratica le equazioni ricorsive che si incontrano sono definite sui numeri reali (si pensi al calcolo della complessità di un algoritmo, ossia il numero di passi necessario per ottenere l'output in funzione dell'input), può essere comodo ambientare il problema nel campo dei numeri complessi. Nel seguito denoteremo con $\mathbb K$ un campo che può essere o quello dei numeri reali o quello dei numeri complessi.

Supponiamo allora di avere fissata l'equazione ricorsiva (27), ossia di aver fissati $a_0,\dots,a_{k-1}\in \mathbb K$ e di cercare le successioni $x\in\mathbb K ^\mathbb N$ che verificano la (27). Sia

$${\cal V}=\{x\in\mathbb K ^\mathbb N\mid x_{n+k}=\sum_{i=0}^{k-1} a_i x_{n+i} \quad \forall n\ge0\}$$

Proposizione 19.2   L'insieme $\cal V$ è uno spazio vettoriale (i.e. è un sottospazio di $\mathbb K ^\mathbb N$.

Dim.  Siano $x,y\in {\cal V}$ allora per ogni n si ha $x_{n+k}=\sum_{i=0}^{k-1} a_i x_{n+i}$ e $y_{n+k}=\sum_{i=0}^{k-1} a_i y_{n+i}$ sommando membro a membro si ha allora che

$$x_{n+k}+y_{n+k}=\sum_{i=0}^{k-1} a_i x_{n+i}+\sum_{i=0}^{k-1} a_i y_{n+i} = \sum_{i=0}^{k-1} a_i (x_{n+i}+ y_{n+i})$$

ossia

$$(x+y)_{n+k}=\sum_{i=0}^{k-1} a_i (x+ y)_{n+i}$$

ossia $x+y\in {\cal V}$. Analogamente se $\lambda\in\mathbb K$ e $x\in {\cal V}$ si ha

$$(\lambda x)_{n+k}=\lambda x_{n+k}=\lambda \sum_{i=0}^{k-1} a_... ...-1} a_i \lambda x_{n+i}=\sum_{i=0}^{k-1} a_i (\lambda x)_{n+i}$$

ossia $\lambda x\in {\cal V}$.     $\square$