Successioni per ricorrenza

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
alegh
Messaggi: 143
Iscritto il: 10 giu 2015, 21:38

Successioni per ricorrenza

Messaggio da alegh »

Nel test finale del senior 2015 tra i quesiti brevi viene proposto il seguente quesito:
data la successione per ricorrenza
\[
\begin{cases}
x_{0}=0\\
x_{n+1}=2x_{n}+n
\end{cases}
\]
determinare la cifra delle unità di $x_{2015}$.
Siccome è una successione per ricorrenza in dipendenza solo del termine precedente, cioè della forma $x_{n+1}=\alpha x_{n}+\beta$ con $\alpha\neq 1$ avrò
\[
x_{n}=\alpha^{n} x_{0}+\dfrac{\alpha^{n}-1}{\alpha -1}\beta
\]
Quindi
\[
x_{2015}=2^{2015}\cdot 0+\dfrac{2^{2015}-1}{2-1}\cdot2015=(2^{2015}-1)\cdot 2015
\]
$2^{2015}-1$ chiaramente è dispari, chiaramente $5|2015$, quindi $(2^{2015}-1)\cdot 2015\equiv 5$ $(mod$ $10)$.
Tuttavia il risultato così trovato risulta errato. Nelle soluzioni è scritto che si giunge alla ricorsione $x_{n}=2^{n}-n-1$, da cui $x_{2015}\equiv 2^{2015}-2016\equiv 2^{3}-6\equiv 2$ $(mod$ $10)$
Dove sbaglio?
Grazie per qualsiasi aiuto
darkcrystal
Messaggi: 706
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Re: Successioni per ricorrenza

Messaggio da darkcrystal »

In un'espressione come $x_{n+1}=\alpha x_n + \beta$ si intende che $\alpha, \beta$ siano costanti, cosa che non è vera in questo esempio (la quantità che aggiungi, $\beta=n$, cambia ad ogni passo). In particolare la tua formula per $x_n$ è falsa, come puoi facilmente vedere: la vera successione comincia $0, 0, 1, 4,...$ mentre la tua formula, se (come mi sembra) la usi con $\beta=n$, ti dà $0, 1, 6, ...$. Qui l'abilità del solutore sta proprio nel trovare una formula chiusa per $x_n$, nonostante la ricorrenza non sia di un tipo completamente "standard".
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: Successioni per ricorrenza

Messaggio da scambret »

Per una trattazione più dettagliata sulle successioni per ricorrenza non standard puoi vedere una qualunque lezione A3 medium del senior, ad esempio http://olimpiadi.dm.unibo.it/videolezio ... um%2FVideo

In generale comunque si sa risolvere qualcosa del tipo $x_{n+2}=ax_{n+1}+bx_{n}$ o cose di questo tipo (se non sai come fare, A3 basic).

La cosa difficile è risolvere cose della forma $x_{n+2}=ax_{n+1}+bx_{n}+f(n)$, dove $f(n)$ è una funzione in $n$ che tendenzialmente è un polinomio o una esponenziale. Tutte le soluzioni della successione non standard sono della forma $y_{sol}=y_0+y_1$ dove $y_1$ sono tutte le soluzioni di quella standard (dove $f(n)=0$ per ogni $n$), mentre $y_0$ è una soluzione che hai trovato tu dell'equazione con $f(n)$, una soluzione "speciale".

Da qui però ci sono troppe considerazioni e troppa euristica. Ti faccio solo vedere come si risolveva quella del Senior ragionandoci su.

Prima risolvi quella generale, cioè $x_{n+1}=2x_n$, che quindi si sa che $x_n=2^n \alpha$.
Ora trovi una soluzione particolare della soluzione con $x_{n+1}=2x_n+n$. Beh dato che $f(n)$ è un polinomio di primo grado, provo a mettere $x_n=cn+d$ e vedere se trovo soluzione. Sostituendo ho $cn+c+d=2cn+2d+n$, dunque $c=-1$ e $d=-1$.

Perciò la soluzione generale è della forma $2^n \alpha - n - 1$. Dalla condizione $x_0=0$ trovi che $\alpha=1$ e dunque $x_n=2^n-n-1$
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Successioni per ricorrenza

Messaggio da fph »

In alternativa: che successione per ricorrenza soddisfa $x_{n+1}-x_n$?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Successioni per ricorrenza

Messaggio da Lasker »

Una possibilità ancora diversa (di solito più brutta...) è trovare la ogf della successione!

Chiamiamo $G(x)=\sum_{n=0}^{\infty}a_nx^n$ e moltiplichiamo entrambi i membri della ricorsione per $x^n$ e sommiamo su $n$ che varia tra $0$ e infinito:
$$\sum_{n=0}^{\infty}a_{n+1}x^n=2\sum_{n=0}^{\infty}a_nx^n+\sum_{n=0}^{\infty}nx^n$$
Scrivendo questa identità in termini di $G(x)$ ottengo:
$$\frac{G(x)-a_0}{x}=2G(x)+x\cdot \frac{d}{dx}\left(\sum_{n=0}^{\infty}x^n\right)=2G(x)+x\cdot \frac{d}{dx}\left(\frac{1}{1-x}\right)=2G(x)+\frac{x}{(1-x)^2}$$
Da qui possiamo ricavare $G(x)$ risolvendo un'equazione di primo grado
$$G(x)=\frac{x^2}{(1-x)^2(1-2x)}+\frac{a_0}{1-2x}=\frac{x^2}{(1-x)^2(1-2x)}+0$$
Spezziamo come somma di frazioni il RHS con numeratore costante (come quando si integra una funzione razionale con il metodo di Hermite o si telescopizza una somma di funzioni razionali):
$$G(x)=\frac{x^2}{(1-x)^2(1-2x)}=-\frac{1}{(1-x)^2}+\frac{1}{1-2x}$$
Riscriviamo queste funzioni razionali come somma di potenze (sfruttando il fatto che serie geometriche & affini sono note...) e cerchiamo il coefficiente di $x^n$, che è proprio $a_n$:
$$G(x)=-\sum_{n=0}^{\infty}(n+1)x^{n}+\sum_{n=0}^{\infty}(2x)^n$$
Da cui si vede subito che il coefficiente di $x^n$ di $G(x)$ è $a_n=2^n-(n+1)$
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
Rispondi