Ricorrere

[Raffa20001]

Una successione è definita ponendo$ x_0 = 0$ e poi per ricorrenza $x_{n+1} = 2x_n + n$.
Determinare la cifra delle unità di $x_{2015}$.

[Bokonon]

$x_2015=2^(2015)-2016$ ed è composto da 607 cifre

[axpgn]

$9$

Ho fatto così ... mi sono calcolato i primi termini e ho visto che ad un certo punto iniziava a ripetersi, difatti compie un ciclo lungo $20$.
Quindi il quindicesimo termine finisce con $9$

Cordialmente, Alex

[Raffa20001]

@axpgn e @Bokonon

Il risultato di Bokonon è corretto, purtroppo quello di axpgn no, anche perchè due numeri pari sottratti tra loro non danno mai un dispari, ma sono sicuro che è stato solo un errore di conto

Più che altro mi interessava capire come arrivare ad ottenere la formula chiusa, perchè in generale non ricordo come si affrontano questi tipi di problemi in cui si chiede di trovare formule chiuse data una ricorrenza.

[hydro1]

"zimmerusky":

Più che altro mi interessava capire come arrivare ad ottenere la formula chiusa, perchè in generale non ricordo come si affrontano questi tipi di problemi in cui si chiede di trovare formule chiuse data una ricorrenza.

Questo è abbastanza facile per induzione: fai un po' di tentativi "a ritroso" per calcolare $x_n$ in funzione di $x_{n-i}$ per qualche $i$ piccolo e ti trovi a congetturare che $x_n=2^{n-2}+\sum_{i=0}^{n-3}2^i(n-i-1)$, per $n$ almeno $3$. Adesso provi questo claim per induzione e poi usi le formule standard per le somme di serie aritmetiche e geometriche e ti ritrovi che $x_n=2^n-n-1$. Adesso calcolare la cifra delle unità è facile: siccome $2^5\equiv 2\mod 10$ e $2015\equiv 3\mod 4$, dev'essere $x_{2015}\equiv 2^3-6=2\mod 10$

[Bokonon]

@zimmerusky

Ci sono tanti modi per risolvere le equazioni ricorsive e dipendono anche dal tipo di ricorsività.
Quando le equazioni sono lineari e del genere $x_n=kx_(n-1)+f(n)$, allora calcolare le differenze di ordine k è raccomandabile.
Per esempio, per la specifica ricorsività, ho fatto:
$a=x_(n+1)=2x_n+n$ quindi $b=x_n=2x_(n-1)+(n-1)$
Da cui $a-b=[x_(n+1)-x_n]-[x_n-x_(n-1)]=x_n-x_(n-1)+1=x_(n-1)+n$
È facile calcolare e dimostrare per induzione che $[x_(n+1)-x_n]-[x_n-x_(n-1)]=2^(n-1)$
Ho sostituito e il resto è immediato.

P.S. axpgn aveva capito male perché ti sei espresso male
Avresti dovuto scrivere "quante cifre compongono il numero $x_2015$?".
Alex avrebbe sbagliato comunque perché l'ultima cifra è 2

[axpgn]

Scusate ma so ancora leggere; cosa ha scritto qui?

"zimmerusky":Determinare la cifra delle unità di $x_{2015}$.

Cosa c'entra il numero di cifre?

E poi non ho sbagliato perché ho trovato la soluzione di $ x_{n+1} = 2x_n + (n+1) $.



Cordialmente, Alex

[Raffa20001]

Il testo non chiede il numero di cifre, ma soltanto l'ultima cifra.

"axpgn":
E poi non ho sbagliato perché ho trovato la soluzione di $ x_{n+1} = 2x_n + (n+1) $.

Ma qui era richiesta l'ultima cifra, in formula chiusa, di $x_n=2^n-n-1$ come giustamente hanno detto Bokonon e hydro