OliForum Matematico

funzioni generatrici

Chiamo $f(n)$ il numero di cambi di n cents possibili, e $g(n)=f(n)-f(n-1)$.
Consideriamo come aumentano i modi di cambiare $n$ cent rispetto a quelli con $n-1$ cent. Per ogni modo di cambiare $n-1$ cent posso associare uno e un solo modo di cambiare $n$ cent semplicemente aggiungendo una moneta da un centesimo. Non posso fare l'inverso, in quanto non in tutti i modi di cambiare $n$ cent ho una moneta da un centesimo da rimuovere: quindi il numero di modi aumenta tanto quanti sono i modi di cambiare $n$ cent utilizzando solo monete da 2 e 3 cent. Questa quantità è $g(n)$.

Cerchiamo ora di determinare $g(n+1)-g(n)$. Come sopra, definisco una relazione che associa elementi dall'insieme delle combinazioni di $n$ cent a elementi dell'insieme di combinazioni di $n+1$ cent, in modo che l'elemento dell'insieme di arrivo abbia una moneta da 3 cent al posto di una da 2 cent rispetto al "collega" dell'insieme di partenza. Restano fuori da questa associazione:
1. nell'insieme degli n cent, tutte le combinazioni formate da solo monete da 3 cent (non ho monete da 2 cent da sostituire)
2. nell'insieme degli n+1 cent, tutte le combinazioni formate da solo monete da 2 cent.
Quindi la differenza tra le cardinalità degli insiemi è $g(n+1)-g(n) = m_2(n+1)-m_3(n)$, dove con $m_k(n)$ indico i modi di cambiare n monete usando solo monete da k cent, e questo vale ovviamente 1 se $k\mid n$, 0 altrimenti.

Comincio ora a scrivere quello che ho trovato:
$g(n+1)-g(n) = m_2(n+1)-m_3(n)$
$g(n+2)-g(n+1) = m_2(n+2)-m_3(n+1)$
.....
$g(n+6)-g(n+5) = m_2(n+6)-m_3(n+5)$

Sommando tutto membro a membro ho che
$g(n+6)-g(n) = \sum_{i=n}^{n+5}m_2(i+1)-m_3(i)$
Siccome prendo 6 valori consecutivi sia di $m_2$ che di $m_3$, è ovvio che nel caso di $m_2$ 3 dei 6 numeri restituiranno 1, e nel caso di $m_3$ 2 dei 6 numeri daranno 1 (in sei numeri consecutivi ci sono tre multipli di due e due multipli di tre).
Quindi rimane $g(n+6)-g(n)=3-2=1$

C'è quindi una certa regolarità nella differenza tra un valore di f(n) e l'altro: basta trovare i primi 6 numeri e poi usare la formula di ricorrenza trovata sopra e quindi abbiamo che la sequenza della funzione $g(n)$ è: 0,1,1,1,1,2, 1,2,2,2,2,3, 2,3,3,3,3,4......

Sia $h(n)$ la funzione della tesi (coi valori arrotondati).
Calocolo la differenza tra due valori di h(n) distanti 6 unità:
$\displaystyle \frac{(n+3)^2}{12}-\frac{(n-6+3)^2}{12}=\frac{n^2+6n+9-n^2+6n-9}{12}=n$

Calcolando a mano i primi sei valori della funzione $h(n)$ vediamo che sale come quella descritta nel post precedente: utilizzando la relazione sopra,
abbiamo che $h(n)-h(n-6)=n$ e $h(n+1)-h(n-5)=n+1$; sia ora $g'(n)=h(n)-h(n-1)$
Abbiamo che $h(n+1)-h(n)-(h(n-5)-h(n-6))=n+1-n \Rightarrow g'(n+1)-g(n-5)=1$
Quindi la funzione h(n) sale esattamente in modo uguale a $f(n)$, come descritto dalle funzioni $g(n)$ e $g'(n+1)$ che sono uguali, quindi sono anch'esse uguali.