Cómo calcular la suma [matemática] \ sum_ {k} \ dbinom {\ lfloor \ frac {n + k} {2} \ rfloor} {k} [/ math]

Deje [math] f (n) = \ sum_ {k = 0} ^ n {\ left \ lfloor {\ frac {n + k} {2}} \ right \ rfloor \ elegir k} [/ math]. Mostraremos que para todos [matemáticas] n \ ge 0, f (n) + f (n + 1) = f (n + 2) [/ matemáticas].

Para hacerlo, observe que

[matemáticas] f (n) + f (n + 1) [/ matemáticas]

[matemáticas] = \ sum_ {k = 0} ^ n {\ left \ lfloor {\ frac {n + k} {2}} \ right \ rfloor \ elegir k} + \ sum_ {k = 0} ^ {n + 1} {\ left \ lfloor {\ frac {n + 1 + k} {2}} \ right \ rfloor \ elegir k} [/ math]

[matemáticas] = {\ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ elegir 0} + \ sum_ {k = 1} ^ n {\ left \ lfloor {\ frac {n + k} {2}} \ right \ rfloor \ elegir k} + \ sum_ {k = 0} ^ {n + 1} {\ left \ lfloor {\ frac {n + 1 + k} {2}} \ right \ rfloor \ elija k} [/ math]

[matemáticas] = 1 + \ sum_ {k = 0} ^ {n-1} {\ left \ lfloor {\ frac {n + k + 1} {2}} \ right \ rfloor \ elija k + 1} + \ sum_ {k = 0} ^ {n + 1} {\ left \ lfloor {\ frac {n + 1 + k} {2}} \ right \ rfloor \ elegir k}. [/ math]

Ahora recuerde la identidad de Pascal:

[matemáticas] {n \ elegir r} + {n \ elegir r + 1} = {n + 1 \ elegir r + 1}. [/ matemáticas]

Entonces, se deduce que la suma anterior es igual a

[matemáticas] = 1 + \ sum_ {k = 0} ^ {n-1} {\ left \ lfloor {\ frac {n + k + 1} {2}} \ right \ rfloor + 1 \ elegir k + 1} + \ sum_ {k = n} ^ {n + 1} {\ left \ lfloor {\ frac {n + 1 + k} {2}} \ right \ rfloor \ elegir k}. [/ math]

Ahora, observamos que

[matemáticas] 1 = {\ left \ lfloor {\ frac {(n + 2) +0} {2}} \ right \ rfloor \ elegir 0}. [/ math]

Adicionalmente,

[matemática] {\ left \ lfloor {\ frac {n + 1 + n} {2}} \ right \ rfloor \ choose n} = {n \ choose n} = {n + 1 \ elegir n + 1} [/ matemáticas]

[matemáticas] = {\ left \ lfloor {\ frac {2n + 3} {2}} \ right \ rfloor \ elegir n + 1} = {\ left \ lfloor {\ frac {(n + 2) + (n + 1)} {2}} \ right \ rfloor \ elegir n + 1} [/ math]

y

[matemáticas] {\ left \ lfloor {\ frac {n + 1 + (n + 1)} {2}} \ right \ rfloor \ choose n + 1} = {n + 1 \ elegir n + 1} = {n +2 \ elegir n + 2} [/ matemáticas]

[matemáticas] = {\ left \ lfloor {\ frac {2n + 4} {2}} \ right \ rfloor \ elegir n + 2} = {\ left \ lfloor {\ frac {(n + 2) + (n + 2)} {2}} \ right \ rfloor \ elegir n + 2}. [/ Math]

Finalmente,

[matemáticas] \ sum_ {k = 0} ^ {n-1} {\ left \ lfloor {\ frac {n + k + 1} {2}} \ right \ rfloor + 1 \ elegir k + 1} [/ math ]

[matemáticas] = \ sum_ {k = 1} ^ {n} {\ left \ lfloor {\ frac {n + k} {2}} \ right \ rfloor + 1 \ elegir k} = \ sum_ {k = 1} ^ {n} {\ left \ lfloor {\ frac {(n + 2) + k} {2}} \ right \ rfloor \ elegir k} [/ math]

Entonces, cuando combinamos todo, tenemos

[matemáticas] f (n) + f (n + 1) [/ matemáticas]

[matemáticas] = 1 + \ sum_ {k = 0} ^ {n-1} {\ left \ lfloor {\ frac {n + k + 1} {2}} \ right \ rfloor + 1 \ elegir k + 1} + \ sum_ {k = n} ^ {n + 1} {\ left \ lfloor {\ frac {n + 1 + k} {2}} \ right \ rfloor \ elegir k} [/ math]

[matemáticas] = {\ left \ lfloor {\ frac {(n + 2) +0} {2}} \ right \ rfloor \ elegir 0} + \ sum_ {k = 1} ^ {n} {\ left \ lfloor {\ frac {(n + 2) + k} {2}} \ right \ rfloor \ elegir k} [/ math]

[matemáticas] + {\ left \ lfloor {\ frac {(n + 2) + (n + 1)} {2}} \ right \ rfloor \ elegir n + 1} + {\ left \ lfloor {\ frac {( n + 2) + (n + 2)} {2}} \ right \ rfloor \ elegir n + 2} [/ math]

[matemáticas] \ sum_ {k = 0} ^ {n + 2} {\ left \ lfloor {\ frac {(n + 2) + k} {2}} \ right \ rfloor \ elegir k} = f (n + 2), [/ matemáticas]

como se desee.

Ahora, todo lo que tenemos que hacer es encontrar los dos primeros valores. Claramente,

[matemáticas] f (0) = \ sum_ {k = 0} ^ 0 {\ left \ lfloor {\ frac {0 + k} {2}} \ right \ rfloor \ choose k} = 1 [/ math]

y

[matemáticas] f (1) = \ sum_ {k = 0} ^ 1 {\ left \ lfloor {\ frac {1 + k} {2}} \ right \ rfloor \ elegir k} = 1 + 1 = 2. [ /matemáticas]

Por lo tanto, se deduce que la secuencia [matemáticas] \ {f (0), f (1), \ ldots \} [/ matemáticas] es una versión desplazada de la secuencia de Fibonacci, y que

[matemáticas] f (n) = \ sum_ {k = 0} ^ n {\ left \ lfloor {\ frac {n + k} {2}} \ right \ rfloor \ choose k} = F_ {n + 2}. [/matemáticas]

(La secuencia de Fibonacci se define por [matemática] F_1 = F_2 = 1 [/ matemática] y, para todos los positivos [matemática] n, F_ {n + 2} = F_ {n + 1} + F_n [/ matemática].)