Fibonacci e binomiali

[FeddyStra]

Siano $ F_n $ i numeri di Fibonacci (si intende come al solito $ F_0=0,F_1=1,F_2=1,F_3=2,\dots $).
Calcolare $ \displaystyle s(m,n,t)=\sum_{k=0}^n \binom{n}{k}F_t^kF_{t-1}^{n-k}F_{m+k} $, dove $ m,n,k,t\in\mathbb N $.

[FeddyStra]

Non ditemi che è troppo difficile!

[kn]

Fa $ ~F_{nt+m} $?

P.S.:

ODIO chi risponde ai problemi con la risposta senza la dimostrazione.

[kn]

Ho fatto delle prove numeriche e sembra che funzioni, quindi scrivo la dimostrazione prima di dimenticarmela:

Innanzitutto dimostriamo per induzione un'altra formula carina che ho trovato strada facendo:
$ \displaystyle~F_{a+2b}=\sum_{i=0}^b\binom{b}{i}F_{a+b} $
Passo base: per $ \displaystyle~j=0 $ abbiamo banalmente $ \displaystyle~F_a=F_a $
Passo induttivo: supponiamo che la formula sia valida per $ \displaystyle~b=c-1 $: $ \displaystyle~\sum_{i=0}^c \binom{c}{i}F_{a+c} $$ \displaystyle~=F_a+\sum_{i=1}^{c-1}\left(\binom{c-1}{i-1}+\binom{c-1}{i}\right)F_{a+i}+F_{a+c}= $
$ \displaystyle~=F_a+F_{a+c}+\sum_{i=0}^{c-2}\binom{c-1}{i}F_{a+i+1}+\sum_{i=1}^{c-1}\binom{c-1}{i}F_{a+i} $$ \displaystyle~=\sum_{i=0}^{c-1}\binom{c-1}{i}F_{(a+1)+i}+\sum_{i=0}^{c-1}\binom{c-1}{i}F_{a+i} $$ \displaystyle~=F_{(a+1)+2c-2}+F_{a+2c-2}=F_{a+2c} $

Per $ \displaystyle~a=m+n-j $ e $ \displaystyle~b=j $ otteniamo $ \displaystyle~\sum_{i=0}^j\binom{j}{i}F_{m+n-j+i}=F_{m+n+j} $. Ponendo infine $ \displaystyle~k=i+n-j $ (da cui $ \displaystyle~i=k+j-n $):
$ \displaystyle~\sum_{0\le k+j-n\le j}\binom{j}{k+j-n}F_{m+k}=F_{m+n+j} $, ovvero $ \displaystyle~\sum_{k=n-j}^n\binom{j}{k+j-n}F_{m+k}=F_{m+n+j} $ (identità che ci servirà tra poco)

Ora il problema: $ \displaystyle~s(m,n,t)=\sum_{k=0}^n \binom{n}{k}F_t^kF_{t-1}^{n-k}F_{m+k} $
Mostriamo che $ \displaystyle~s(m,n,t+1)=s(m+n,n,t) $
$ \displaystyle~\sum_{k=0}^n\binom{n}{k}F_{t+1}^k F_t^{n-k}F_{m+k} $$ \displaystyle~=\sum_{k=0}^n\binom{n}{k}(F_t+F_{t-1})^k F_t^{n-k}F_{m+k} $$ \displaystyle~=\sum_{k=0}^n\sum_{j=0}^k\binom{n}{k}\binom{k}{j}F_t^{k-j}F_{t-1}^j F_t^{n-k}F_{m+k}= $
$ \displaystyle~=\sum_{k=0}^n\sum_{j=0}^k\binom{n}{k}\binom{k}{j}F_t^{n-j}F_{t-1}^j F_{m+k} $$ \displaystyle~=\sum_{j=0}^n\sum_{k=j}^n\binom{n}{k}\binom{k}{j}F_t^{n-j}F_{t-1}^j F_{m+k} $$ \displaystyle~=\sum_{j=0}^n\binom{n}{j}F_t^{n-j}F_{t-1}^j\sum_{k=j}^n\binom{n-j}{k-j}F_{m+k}= $
$ \displaystyle~=\sum_{j=0}^n\binom{n}{n-j}F_t^{n-j}F_{t-1}^{n-(n-j)}\sum_{k=n-(n-j)}^n\binom{n-j}{k+(n-j)-n}F_{m+k} $$ \displaystyle~=\sum_{0\le n-j\le n}\binom{n}{n-j}F_t^{n-j}F_{t-1}^{n-(n-j)}\sum_{k=n-(n-j)}^n\binom{n-j}{k+(n-j)-n}F_{m+k}= $
(ridefinendo $ \displaystyle~j:=n-j $) $ \displaystyle~=\sum_{j=0}^n\binom{n}{j}F_t^{j}F_{t-1}^{n-j}\sum_{k=n-j}^n\binom{j}{k+j-n}F_{m+k}= $ (per quanto dimostrato sopra)
$ \displaystyle~=\sum_{j=0}^n\binom{n}{j}F_t^{j}F_{t-1}^{n-j}F_{m+n+j}=s(m+n,n,t) $
Possiamo quindi affermare che $ \displaystyle~s(m,n,t)=s(m+n(t-1),n,1) $.
Notiamo ora che $ \displaystyle~s(m+2,n,t)=s(m+1,n,t)+s(m,n,t) $, infatti
$ \displaystyle~\sum_{k=0}^n\binom{n}{k}F_t^k F_{t-1}^{n-k}F_{m+2+k}=\sum_{k=0}^n\binom{n}{k}F_t^k F_{t-1}^{n-k}(F_{m+1+k}+F_{m+k}) $$ \displaystyle~=\sum_{k=0}^n\binom{n}{k}F_t^k F_{t-1}^{n-k}F_{m+1+k}+\sum_{k=0}^n\binom{n}{k}F_t^k F_{t-1}^{n-k}F_{m+k} $.
Ma $ \displaystyle~s(0,n,1)=F_n $ e $ \displaystyle~s(1,n,1)=F_{n+1} $, quindi $ \displaystyle~s(m,n,1)=F_{n+m} $. Per quanto detto prima $ \displaystyle~s(m,n,t)=s(m+n(t-1),n,1)=F_{n+m+n(t-1)}=F_{nt+m} $

Comunque era un esercizio stupendo! (E un po' bastardo, basta cambiare un indice/esponente in un altro modo e non si riesce più a proseguire! )

[FeddyStra]

Perfetto!