OliForum Matematico

Generalizzazione del Problema 7 del Giornalino 17

Problema
Sia $ a_1,\dots, a_k $ una sequenza finita di interi non negativi. Diciamo che essa è alternante se è crescente e se numeri consecutivi hanno parità opposta (cioè si alternano numeri pari e dispari). Dato $ n\in\mathbb{N} $,trovare il numero $ A(n) $ delle sequenze alternantitali che $ a_i\le n $ per ogni $ i $

EDIT: what aveva perfettamente ragione

Boll ha scritto:Problema
Sia $ a_1,\dots, a_k $ una sequenza finita di interi. Diciamo che essa è alternante se è crescente e se numeri consecutivi hanno parità opposta (cioè si alternano numeri pari e dispari). Dato $ n\in\mathbb{N} $,trovare il numero $ A(n) $ delle sequenze alternantitali che $ a_i\le n $ per ogni $ i $

Uhm... non capisco.
Consideriamo la successione
$ a_1=n-k+1 $
$ a_{i+1}=a_i+1 \textrm{ con } 1\leq i\leq k $.
Essa è alternante, ed inoltre $ a_i\leq n $ per ogni $ i $.
Se pongo $ b_i:=a_i-h $ con $ h $ intero positivo, allora anche la sequenza $ b_1,\dots,b_k $ è alternante e soddisfa le condizioni del problema.
Ma $ h $ può assumere infiniti valori, e quindi $ A(n) $ è sempre infinito...
Dove sbaglio??

Scusa what mancava un ipotesi... Hai perfettamente ragione, solo che nel Giornalino partendo da 1 non si ponevano il problema. Cambio il testo :P

Per ogni n, definiamo :
P(n) :numero di sequenze alternanti valide(tali che $ a_i\leq n $ per ogni i) e tali che l’ultimo numero della sequenza sia pari
D(n) : numero di sequenze alternanti valide e tali che l’ultimo numero della sequenza sia dispari.
Quindi A(n) = P(n) + D(n).

Ora, se n è pari, avremo che:
P(n) = P(n-1)+D(n-1)+1, perché, alle sequenze P(n-1), si devono sommare quelle D(n-1), alle quali viene aggiunto n,ed aggiungere anche la sequenza composta solo da n.
D(n) = D(n-1)

Allo stesso modo, se n è dispari, avremo :
P(n) = P(n-1)
D(n) = P(n-1)+D(n-1)+1

Dimostriamo ora che A(n+2)=A(n+1)+A(n)+2

Se n è dispari:
P(n+1)=P(n)+D(n)+1 D(n+1)=D(n)
P(n+2)=P(n)+D(n)+1 D(n+2)=P(n+1)+D(n+1)+1=P(n)+2D(n)+2

A(n)=P(n)+D(n)
A(n+1)=P(n)+2D(n)+1
A(n+2)=2P(n)+3D(n)+3=A(n)+A(n+1)+2

Se n è pari:
P(n+1)=P(n) D(n+1) = P(n)+D(n)+1
P(n+2)=2P(n)+D(n)+2 D(n+1) = P(n)+D(n)+1

A(n)=P(n)+D(n)
A(n+1)=2P(n)+D(n)+1
A(n+2)=3P(n)+2D(n)+3=A(n)+A(n+1)+2

Quindi:
A(1)=3
A(2)=6
A(n)=A(n-1)+A(n-2)+2

Ora bisogna solo trovare la formula esplicita per A(n), che dovrebbe essere decisamente 'brutta'.Se la soluzione è giusta, magari faccio i conti e la scrivo.

Pare proprio tutto perfetto, la mio soluzione era leggermente diversa... Riguardo alla formula è sicuramente una cosa tanto brutta quanto famosa

Beh, in effetti si tratta di una formula famosa.
Indicato con F(k) il k-esimo numero di Fibonacci, abbiamo che:

$ \begin{displaystyle}A(n)=F(n+4)-2=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+4}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+4}}{\sqrt{5}}-2\end{displaystyle} $

Ezzi, 7 punti per Igor :D

La famosa formula di Binet, detta anche "se non vedi che funziona non ci credi"