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 » 28 apr 2016, 23:18

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: 661
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Re: Successioni per ricorrenza

Messaggio da darkcrystal » 29 apr 2016, 07:44

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: 609
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: Successioni per ricorrenza

Messaggio da scambret » 29 apr 2016, 14:14

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$
"Volevo er milkshake, lo bbevo ogni morte dde papa"
"M anno buttato la crema solare, era de mi mamma"
"Me vie na congestione"
Panini che viaggiano molto velocemente verso la faccia di un tizio che risponde "I'm not hungry"

Aeroporto di Atene, 8 maggio 2015! Ancora nel cuore ITA4

fph
Site Admin
Messaggi: 3283
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Successioni per ricorrenza

Messaggio da fph » 29 apr 2016, 16:05

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: 316
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Successioni per ricorrenza

Messaggio da Lasker » 29 apr 2016, 17:14

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

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite