Binomio Suma, a Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

Question

¿Cómo lo voy a probar

$$ \sum\limits_{\vphantom{\large}i\,,\,j\ \geq\ 0}{n-i \elegir j} {n-j \elegir i} =F_{2n+1} $$

donde $n$ es un entero no negativo y $\{F_n\}_{n\ge 0}$ es una secuencia de números de Fibonacci?

Muchas gracias! :)

Answer 1

Combinatoria prueba 1

$F_{2n+1}$ es el número de azulejos de una $1\times(2n+1)$-rectángulo por las plazas y las fichas de dominó. Cualquier mosaico contiene un número impar de plazas, para que podamos encontrar el medio de la plaza. El número de apuntados con $i$ dominó a la izquierda de esta plaza y $j$ a la derecha (e $n-i-j$ plazas en ambas partes) es exactamente $\binom{n-j}{i\vphantom j}\binom{n-i}j$.

(Cf. combinatoria prueba de $F_n=\sum\binom{n-i}i$.)

---

Combinatoria prueba 2

$F_{2n+1}$ es el número de 00-evitar las secuencias binarias de longitud $2n$. Reclamo: hay $\binom{n-j}i\binom{n-i}j$ tal secuencia con $i$ ceros en lugares extraños y $j$ ceros en incluso los lugares.

(De hecho, tomar una secuencia de longitud $n-j$ $i$ ceros y una secuencia de longitud $n-i$ $j$ ceros; write el primer elemento de la primera secuencia; si es 0 se debe ser seguida por la 1, de lo contrario usar el primer elemento de la segunda secuencia y así sucesivamente; en el extremo usted conseguirá un 00-evitar la secuencia de longitud exactamente $2n$.)

P. S. La última prueba puede ser adaptado para mostrar que $$ 2\sum\binom{n-k}i\binom{n-i}j\binom{n-j}k=F_{3n+2} $$ y así sucesivamente. Los detalles se pueden encontrar en A. Benjamin, J. Rouse, 'Contando Binomio de Fibonacci Identidades, las Aplicaciones de los Números de Fibonacci, Volumen 9 (2003).

P. P. S. Si usted prefiere convención donde $F_0=0$ (en lugar de $F_0=1$), lectura de $F_{2n+2}$ en lugar de $F_{2n+1}$ etc en todas partes a partir de la pregunta.

Answer 2

El problema pide a mostrar que \begin{align} \sum_{i=0}^{n} \sum_{j=0}^{n} \binom{n-i}{j} \binom{n-j}{i} = F_{2n+1}. \end{align} El problema, como se ha dicho, es incorrecta. Debería leer $F_{2n+2}$. Esto será mostrado en la siguiente.

Considere la posibilidad de la doble sumatoria \begin{align} S_{n} = \sum_{i=0}^{n} \sum_{j=0}^{n} \binom{n-i}{j} \binom{n-j}{i}. \end{align} Mediante la inversión de la suma que sobre el índice de $i$ esto se convierte en \begin{align} S_{n} = \sum_{i=0}^{n} \sum_{j=0}^{i} \binom{i}{j} \binom{n-j}{n-i}. \end{align} Ahora considere la posibilidad de la generación de la función de $S_{n}$. \begin{align} \sum_{n=0}^{\infty} S_{n} t^{n} &= \sum_{n=0}^{\infty} \sum_{i=0}^{n} \sum_{j=0}^{i} \binom{i}{j} \binom{n-j}{n-i} \ t^{n} \\ &= \sum_{n=0}^{\infty} \sum_{i=0}^{\infty} \sum_{j=0}^{i} \binom{i}{j} \binom{n+i-j}{n} \ t^{n+i} \\ &= \sum_{i=0}^{\infty} \sum_{j=0}^{i} \binom{i}{j} \ t^{i} \cdot \sum_{n=0}^{\infty} \binom{n+i-j}{n} \ t^{n} \\ &= \sum_{i=0}^{\infty} \sum_{j=0}^{i} \binom{i}{j} \ t^{i} \ (1-t)^{-i+j-1} \\ &= \frac{1}{1-t} \ \sum_{i=0}^{\infty} \left( \frac{t}{1-t} \right)^{i} \cdot \sum_{j=0}^{i} \binom{i}{j} \ (1-t)^{j} \\ &= \frac{1}{1-t} \ \sum_{i=0}^{\infty} \left( \frac{t}{1-t} \right)^{i} \ (2-t)^{i} \\ &= \frac{1}{1-t} \ \sum_{i=0}^{\infty} \left( \frac{2t - t^{2}}{1-t} \right)^{i} \\ &= \frac{1}{1-t} \ \frac{1-t}{1-3t+t^{2}} \\ &= \frac{1}{1-3t+t^{2}}. \end{align} Ahora, \begin{align} \frac{1}{1-3t+t^{2}} &= \frac{1-t}{1-3t+t^{2}} + \frac{t}{1-3t+t^{2}} \\ &= \sum_{n=0}^{\infty} F_{2n+1} \ t^{n} + \sum_{n=0}^{\infty} F_{2n} \ t^{n} \\ &= \sum_{n=0}^{\infty} F_{2n+2} \ t^{n} \end{align} lo cual, comparado con el resultado anterior, conduce a \begin{align} \sum_{i=0}^{n} \sum_{j=0}^{n} \binom{n-i}{j} \binom{n-j}{i} = F_{2n+2}. \end{align}

Answer 3

Una prueba más. Vamos a reescribir la suma en términos de$i$$k=i+j$: $$ \binom{n-i}j\binom{n-j}i=\binom{n-i}{n-k}\binom{n-k+i}{n-k}. $$ Vandermonde de convolución implica $$ \sum_i\binom{n-i}{n-k}\binom{n-k+i}{n-k}=\binom{2n+1-k}{2n+1-2k}; $$ Ahora sólo tenemos que usar bien conocido el hecho de $$ \sum_k\binom{2n+1-k}{2n+1-2k}=F_{2n+1}. $$

Answer 4

Si $S$ es el operador de desplazamiento a la e $F$ es la secuencia de Fibonacci, a continuación,$(S^2-S-1)F=0$. Por lo tanto, $$ \begin{align} (S^4-3S^2+1)F &=(S^2+S-1)(S^2-S-1)F\\ &=(S^2+S-1)\,0\\ &=0\tag{1} \end{align} $$ Por lo tanto, la secuencia de Fibonacci también satisface $$ F_{2n+2}=3F_{2n}-F_{2n-2}\etiqueta{2} $$

---

Vamos $$ f(n)=\sum_{i,j\ge0}^n\binom{n-i}{j}\binom{n-j}{i}\etiqueta{3} $$ Sustituyendo $i\mapsto i-1$ $j\mapsto j-1$ da $$ \begin{align} f(n-1) &=\sum_{i,j\ge0}^{n-1}\binom{n-1-i}{j}\binom{n-1-j}{i}\\ &=\sum_{i,j\ge1}^n\binom{n-i}{j-1}\binom{n-j}{i-1}\tag{4} \end{align} $$ La definición de Triángulo de Pascal, $(3)$, e $(4)$ de rendimiento $$ \begin{align} &f(n+1)\\[9pt] &=\sum_{i,j\ge0}^n\binom{n+1-i}{j}\binom{n+1-j}{i}\\ &=\sum_{i,j\ge0}^n\left[\binom{n-i}{j}+\binom{n-i}{j-1}\right]\left[\binom{n-j}{i}+\binom{n-j}{i-1}\right]\\ &=\sum_{i,j\ge0}^n\color{#C00000}{\binom{n-i}{j}\binom{n-j}{i}}+\color{#00A000}{\binom{n-i}{j-1}^n\binom{n-j}{i}}\\ &+\sum_{i,j\ge0}^n\color{#00A000}{\binom{n-i}{j}\binom{n-j}{i-1}}+\color{#0000FF}{\binom{n-i}{j-1}\binom{n-j}{i-1}}\\ &=\color{#C00000}{f(n)}+\color{#0000FF}{f(n-1)}+\color{#00A000}{2}\sum_{i,j\ge0}^n\color{#00A000}{\binom{n-i}{j}\binom{n-1-j}{i}}\\ &=f(n)+f(n-1)+2\sum_{i,j\ge0}^n\binom{n-i}{j}\left[\binom{n-j}{i}-\binom{n-1-j}{i-1}\right]\\ &=f(n)+f(n-1)+2\sum_{i,j\ge0}^n\left[\binom{n-i}{j}\binom{n-j}{i}-\binom{n-i}{j}\binom{n-1-j}{i-1}\right]\\ &=f(n)+f(n-1)+2\sum_{i,j\ge0}^n\left[\color{#C00000}{\binom{n-i}{j}\binom{n-j}{i}}-\color{#0000FF}{\binom{n-i}{j-1}\binom{n-j}{i-1}}\right]\\[6pt] &=f(n)+f(n-1)+2[\color{#C00000}{f(n)}-\color{#0000FF}{f(n-1)}]\\[18pt] &=3f(n)-f(n-1)\tag{5} \end{align} $$ Recursiones $(2)$ $(5)$ y las condiciones iniciales $f(0)=1$ $f(1)=3$ implica que $$ f(n)=F_{2n+2}\etiqueta{6} $$

Answer 5

$\newcommand{\ángulos}[1]{\left\langle\, nº 1 \,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\, nº 1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, nº 1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, nº 1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\piso}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\norm}[1]{\left\vert\left\vert\, nº 1\,\right\vert\right\vert} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\vphantom{\large Un}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, nº 1 \,\right\vert}$ $\ds{\sum_{\vphantom{\large}k,\,j\ \geq\ 0}{n - k \elegir j}{n - j \elegir k} =F_{2n + 2}:\ {\large ?}}$ where $\ds{F_{m}}$ es un Número Fibonacci.

---

\begin{align}&\color{#66f}{\large% \sum_{\vphantom{\large A}k,\,j\ \geq\ 0}{n - k \choose j}{n - j \choose k}} =\sum_{\vphantom{\large A}k\,,\,j\ \geq\ 0}{n - k \choose j} \oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n - j} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} \end{align}

donde $\ds{\varphi \equiv {1 + \root{5} \over 2}}$ es la Proporción Áurea. A continuación,

\begin{align}&\color{#66f}{\large% \sum_{\vphantom{\large A}k,\,j\ \geq\ 0}{n - k \choose j}{n - j \choose k}} =\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n} \over z} \sum_{k\ =\ 0}^{\infty}{1 \over z^{k}}\ \overbrace{% \sum_{j\ =\ 0}^{\infty}{n - k \choose j}\pars{1 \over 1 + z}^{j}} ^{\dsc{\pars{2 + z \over 1 + z}^{n - k}}}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{2 + z}^{n} \over z} \sum_{k\ =\ 0}^{\infty}\bracks{1 + z \over z\pars{2 + z}}^{k} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{2 + z}^{n} \over z} {1 \over 1 - \pars{1 + z}/\bracks{z\pars{2 + z}}} \,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{2 + z}^{n + 1} \over z^{2} + z - 1} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}} {\pars{2 + z}^{n + 1} \over \pars{z + \varphi}\pars{z - \varphi^{-1}}} \,{\dd z \over 2\pi\ic} ={\pars{2 - \varphi}^{n + 1} \over -\varphi - \varphi^{-1}} +{\pars{2 + \varphi^{-1}}^{n + 1} \over \varphi^{-1} + \varphi} \\[5mm]&={\pars{2 + \varphi^{-1}}^{n + 1} - \pars{2 - \varphi}^{n + 1}\over \root{5}}\quad\mbox{because}\quad \varphi^{-1} + \varphi=\root{5} \end{align}

Por otra parte

$$ \raíz{2 + \varphi^{-1}}=\varphi\quad\mbox{y}\quad \raíz{2 - \varphi}=\varphi^{-1} $$

tal que

\begin{align}&\color{#66f}{\large% \sum_{\vphantom{\large A}k,\,j\ \geq\ 0}{n - k \choose j}{n - j \choose k}} ={\varphi^{2n + 2} - \pars{-\varphi}^{-2n - 2} \over \root{5}} =\color{#66f}{\large F_{2n + 2}} \end{align}