Ejercicios sobre números de Fibonacci

Question

Considerar positiva $n$, la identidad

$$ x^n = \sum_{k=1}^{n} F_{n,k} \, x^{\left(1+ \left\lceil \frac{k-1}{2} \right\rceil\right)} (x-1) ^{\left\lfloor \frac{k-1}{2}\right\rfloor}$$

y probar que la suma $F_n= F_{n,1} + F_{n,2} + \cdots + F_{n,n}$ $n$-ésimo número de Fibonacci satisfaciendo el % de relaciones $F_1 = F_2 = 1$y $F_n = F_{n-1} + F_{n-2}$ $n>2$.

¿Alguien sabe cómo solucionarlo?

¡¡Muchas gracias!!

Answer 1

Esto no es probable que la mayoría de la prueba directa, sino que debe arrojar algo de luz sobre la cuestión. La tabla de la $F_{n,k}$ números pueden ser generados por este simple programa de MATLAB

function table = fibtable(nrows)
  table = zeros(nrows);
  for n = 1:nrows
    M = fibident(n);
    row = M \ [zeros(n-1,1); 1];
    table(n,1:n) = row.';
  end
end

function M = fibident(n)
  M = zeros(n);
  for k=1:n
    a = 1 + ceil((k-1)/2);
    b = floor((k-1)/2);
    for d = 0:b
      M(a+d, k) = (-1).^(b-d) * nchoosek(b,d);
    end
  end
end

El programa se basa en la observación, realizada también en los comentarios a la pregunta, que la identidad debe ser interpretado como la identidad de dos polinomios de variable real. Para el 18 de filas, obtenemos

$$\scriptsize \begin{matrix} 1 \\ 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 2 & 1 \\ 0 & 1 & 1 & 3 & 2 & 1 \\ 0 & 1 & 1 & 4 & 3 & 3 & 1 \\ 0 & 1 & 1 & 5 & 4 & 6 & 3 & 1 \\ 0 & 1 & 1 & 6 & 5 & 10 & 6 & 4 & 1 \\ 0 & 1 & 1 & 7 & 6 & 15 & 10 & 10 & 4 & 1 \\ 0 & 1 & 1 & 8 & 7 & 21 & 15 & 20 & 10 & 5 & 1 \\ 0 & 1 & 1 & 9 & 8 & 28 & 21 & 35 & 20 & 15 & 5 & 1 \\ 0 & 1 & 1 & 10 & 9 & 36 & 28 & 56 & 35 & 35 & 15 & 6 & 1 \\ 0 & 1 & 1 & 11 & 10 & 45 & 36 & 84 & 56 & 70 & 35 & 21 & 6 & 1 \\ 0 & 1 & 1 & 12 & 11 & 55 & 45 & 120 & 84 & 126 & 70 & 56 & 21 & 7 & 1 \\ 0 & 1 & 1 & 13 & 12 & 66 & 55 & 165 & 120 & 210 & 126 & 126 & 56 & 28 & 7 & 1 \\ 0 & 1 & 1 & 14 & 13 & 78 & 66 & 220 & 165 & 330 & 210 & 252 & 126 & 84 & 28 & 8 & 1 \\ 0 & 1 & 1 & 15 & 14 & 91 & 78 & 286 & 220 & 495 & 330 & 462 & 252 & 210 & 84 & 36 & 8 & 1 \end{de la matriz} $$

It then becomes apparent that the columns of the table (except the first) are the diagonals of Pascal's triangle, which are related to the Fibonacci numbers (See, for example, here.) In particular,

$$ F_{n,k} = \binom{n-\left\lceil \frac{k}{2}\right\rceil - 1}{n-k} \enspace,$$

which holds for $1 \leq k \leq n$ if we stipulate that $\binom{a}{b} = 0$ when $b < 0$ and $\binom{un}{0} = 1$ also for negative $un$.

---

Let $S_n = \sum_{1 \leq k \leq n} F_{n,k}.$ It's easy to verify that $S_n = F_n$ for $1 \leq n \leq 3$. We show that $S_{n+2} = S_{n} + S_{n+1}$ for $n > 1$, hence proving that $S_n = F_n$ for all positive $n$.

Taking into account that $F_{n,1} = 0$ and $F_{n,2} = F_{n,n} = 1$ for all $n > 1$, we line up the appropriate members of the two sums and then apply the basic identity,

$$ \binom{a}{b} + \binom{a}{b+1} = \binom{a+1}{b+1} \enspace,$$

which holds for $0 \leq b \leq un$. In detail,

$$\begin{align} S_n + S_{n+1} &= \sum_{1 \leq k \leq n-1} \binom{n - \left\lceil \frac{k}{2} \right\rceil - 1}{n-k} + \sum_{1 \leq k \leq n+1} \binom{n + 1 - \left\lceil \frac{k}{2} \right\rceil - 1}{n+1-k} + 1 \\ &= 0 + 1 + \sum_{3 \leq k \leq n+1} \binom{n + 1 - \left\lceil \frac{k}{2} \right\rceil - 1}{n+2-k} + \sum_{3 \leq k \leq n+1} \binom{n + 1 - \left\lceil \frac{k}{2} \right\rceil - 1}{n+1-k} + 1 \\ &= 0 + 1 + \sum_{3 \leq k \leq n+1} \left[ \binom{n + 1 - \left\lceil \frac{k}{2} \right\rceil - 1}{n+2-k} + \binom{n + 1 - \left\lceil \frac{k}{2} \right\rceil - 1}{n+1-k}\right] + 1 \\ &= F_{n+2,1} + F_{n+2,2} + \sum_{3 \leq k \leq n+1} \binom{n + 2 - \left\lceil \frac{k}{2} \right\rceil - 1}{n+2-k} + F_{n+2,n+2} \\ &= \sum_{1 \leq k \leq n+2} \binom{n + 2 - \left\lceil \frac{k}{2} \right\rceil - 1}{n+2-k} \\ &= S_{n+2} \enspace. \end{align}$$

---

Inspection of the matrix above suggested a formula for $F_{n,k}$. It remains to prove that the suggestion was correct. We'll start by revisiting the program that produces the table of the $F_{n,k}$ coefficients.

If we look at a few matrices produced by fibident, we'll see that they have a very interesting structure:

$$\pequeño M_5 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} ~~~~~~ M_7 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & -2 & 1 & -1 \\ 0 & 0 & 0 & 0 & 1 & -2 & 3 \\ 0 & 0 & 0 & 0 & 0 & 1 & -3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \enspace. $$ Cada matriz es una submatriz de todas las grandes matrices y las matrices son de forma triangular, con una diagonal de todos (lo que implica que son unimodular). Por lo tanto, sólo necesitamos generar una matriz e invertir para obtener (la transpuesta de) la tabla. (Los lados de la parte derecha de todos nuestros sistemas de ecuaciones lineales son las columnas de la matriz identidad.) Nuestro código revisado.

function [tab, M] = fibmatrices(n)
  M = fibident(n);
  tab = inv(M).';
end

Esta revisión también sugiere que se puede demostrar la veracidad de nuestra hipótesis para los coeficientes en la demostración de que la transpuesta de la matriz definida por nuestra $F_{n,k}$'s es la inversa de la $M$ de la matriz anterior. Podemos escribir la expresión del elemento genérico $P_{i,j}$ del producto de las dos matrices y, después de una cantidad no trivial de álgebra, nos encontramos con que $P_{i,i} = 1$ $P_{i,j} = 0$ siempre $i \neq j$.

En algo más de detalle, empezamos por observar que las columnas de a $M$ contienen los coeficientes de $(x-1)^{\left\lfloor \frac{k-1}{2} \right\rfloor}$; por lo tanto

$$ M_{n,k} = (-1)^{k-n} \binom{\left\lfloor \frac{k-1}{2} \right\rfloor}{n - \left\lceil \frac{k+1}{2} \right\rceil} = (-1)^{k-n} \binom{\left\lfloor \frac{k-1}{2} \right\rfloor}{k-n} \enspace. $$

We then write, for $i,j>1$,

$$ P_{i,j} = \sum_{i \leq k \leq j} F_{k,i} M_{k,j} = \sum_{i \leq k \leq j} (-1)^{j-k} \binom{k - \left\lceil \frac{i}{2} \right\rceil}{k-i} \binom{\left\lfloor \frac{j-1}{2} \right\rfloor}{j-k} \enspace. $$

In preparation for further manipulation, we write,

$$ P_{i,j} = (-1)^j \sum_{i \leq k \leq j} (-1)^k \binom{\left\lfloor \frac{j-1}{2} \right\rfloor}{k- \left\lceil \frac{j-1}{2} \right\rceil - 1} \binom{k - \left\lceil \frac{i}{2} \right\rceil - 1}{\left\lfloor \frac{i}{2} \right\rfloor - 1} \enspace. $$

Now we spit cases; for $i>j$ the summation is empty and $P_{i,j}=0$. For $i=j$ the summation contains one term,

$$ P_{i,i} = \binom{\left\lfloor \frac{i-1}{2} \right\rfloor}{\left\lfloor \frac{i-1}{2} \right\rfloor} \binom{\left\lfloor \frac{i}{2} \right\rfloor - 1}{\left\lfloor \frac{i}{2} \right\rfloor - 1} = 1 \enspace. $$

Finally, for $j>i$, if $k < \left\lceil \frac{i}{2} \right\rceil + 1$, it is also $k < \left\lceil \frac{j-1}{2} \right\rceil + 1$. Hence, we can safely extend the summation to all values of $k$. This allows us to apply a variation of Vadermonde's convolution ((5.24) in Concrete Mathematics, second edition), which gives,

$$ P_{i,j} = \binom{- \left\lceil \frac{i}{2} \right\rceil + \left\lceil\frac{j-1}{2} \right\rfloor}{\left\lfloor \frac{i}{2} \right\rfloor - \left\lfloor \frac{j-1}{2} \right\rfloor - 1} \enspace. $$

For $j>i$, the upper index is non-negative, and the lower index is always greater than the upper index. Hence $P_{i,j} = 0$.