Demostrar que existen infinitos números enteros tales que a $ \binom{m}{n-1} = \binom{m-1}{n} $

Question

Esta pregunta viene de la 1 de brasil OMI TST de 2004. No he encontrado ningún soluciones de ti en línea, a pesar de que he desarrollado.

Después de llegar a $ mn = (m-n)(m-n+1) $, mi solución se basa en la afirmación de que $ m_z = F(2z) \cdot F(2z+1) $ $ n_z = F(2z-1) \cdot F(2z) $ (donde $ F(z) $ es la función de Fibonacci), que puede ser fácilmente demostrado por inducción finita.

Otro intento me había encuentra que $ n = \dfrac{3m+1 \pm \sqrt{5m^2+2m+1}}{2} $, pero no podía demostrar que existen infinitos números enteros $ m $ tal que $ \sqrt{5m^2+2m+1} $ es un número entero $ \equiv m+1 \pmod2 $.

Notando $ 5m^2+2m+1 = (2m)^2 + (m+1)^2 $, he tratado de establecer una primitiva de Pitágoras triplete $ x^2-y^2=m+1, \; 2xy=2m $, pero no podía probar $ x^2-xy-y^2=1 $ tiene infinitamente muchos entero de soluciones. Sé que esta es una hipérbola y que la beca Pell que me puede ayudar mucho aquí, pero he tratado de contenerme para usar lo que he aprendido en la escuela secundaria.

Alguien puede concluir mi segundo enfoque o me dan una diferente~más fácil?

Answer 1

Para demostrar que $x^2-xy-y^2=1$ tiene infinito número entero de soluciones, se puede ver $ (1,0) $ es una solución; y si $ (a,b) $ es una solución, $ (2a+b,a+b) $ también es. Usted puede encontrar esta relación mediante la observación de los casos pequeños.

Answer 2

He aquí un enfoque explícito de llegar a ali's solución.

Aplicar la fórmula cuadrática a $x^2-xy-y^2-1=0$, buscando no negativo soluciones:

$$y=\frac{-x+\sqrt{x^2+4(x^2-1)}}2=\frac{-x+\sqrt{5x^2+4}}2\;.$$

Claramente este es un número entero al $y\in\{0,1,3\}$, y un poco más de la computación vueltas el siguiente valor entero en $y=8$. Ahora mira en el entero de soluciones descubierto hasta ahora: $\langle 1,0\rangle,\langle 2,1\rangle,\langle 5,3\rangle$, e $\langle 13,8\rangle$. Esos números son muy conocidos: la vuelta a las parejas a su alrededor, y usted tiene $0,1,1,2,3,5,8,13$, es decir, los números de Fibonacci $F_0$ a través de $F_7$. Si denotamos las sucesivas soluciones por $\langle x_n,y_n\rangle$, esto sugiere inmediatamente que $y_{n+1}=x_n+y_n$$x_{n+1}=y_{n+1}+x_n=2x_n+y_n$. Una vez que imagino que esas recurrencias, es un trivial de cálculo para verificar que efectivamente el rendimiento de las soluciones.

Answer 3

Las otras soluciones son buenas. Me gustaría señalar que llegar a $ x^2 - xy - y^2 =1 $ parece casi mágico / hubo varios aros para saltar a través de (relativa a pitágoras, viendo algunos de factorización, etc) . Como tal, es poco probable que esta es la solución buscada. Estoy ofreciendo una alternativa que es más fácil motivar, y lo más probable que a lo largo de las líneas de lo que se espera, porque simplemente "hacer la siguiente cosa".

Vamos a mirar hacia atrás en el orignial ecuación, que es $ mn = (m-n) ( m-n+1) $. Esta es una sección cónica, en particular, una hipérbola, y la gente tiene miedo de él, porque parece complicado. Lo es, pero sólo porque el eje no son lo que estamos acostumbrados.

¿Qué es lo siguiente que hay que hacer? Desde que no nos gustan de la cruz, nos convierten en una rectilíneo sistema de coordenadas (que casi siempre lo hacen). En este caso, tomamos el sistema de

$$ a = m+n, b = m- n $$

que nos dará $\frac{ a+b}{2} \times \frac{a-b} { 2} = b(b+1)$, o que $a^2 = 5b^2 + 4 b $. Está claro que $m, n$ son enteros si y sólo si $a, b$ a ser enteros, de la misma paridad. A partir de la ecuación $a^2 = 5b^2 + 4b \equiv b^2 \pmod{4}$, esto es trivialmente satisfecho, así que vamos a ignorar la paridad de condiciones y proceder a resolver para los números enteros.

¿Qué es lo siguiente que hay que hacer? $a ^2 - 5b^2$ parece muy Pellish. ¿Cómo podemos transformar y deshacerse de $4b$? Podemos completar el cuadrado de manera creativa.

$$ 5a^2 = 25b^2 + 20 b = (5b + 2)^2 - 4 $$

Ahora tenemos una ecuación de Pell con $ X = (5b+2), Y = a$, y tenemos

$$ X^2 - 5Y^2 = 4$$

Esto tiene una semilla solución de $ X = 2, Y = 0$ o $X = 3, Y = 1$. Casi hemos terminado, pero necesitamos $ X \equiv 2 \pmod{5}$ a fin de $b$, y entero, y, en particular, $X=3$ no va a funcionar (snif snif).

¿Qué es lo siguiente que hay que hacer? De la teoría de la ecuación de Pell, sabemos que el conjunto de soluciones es $ (2,0) * (9, 4)^n$, con la operación realizada como $ (p,q) * (r,s) = ( pr+5qs, ps+qr)$. Observar que $(9,4) ^2 = (161, 72)$. Tenemos que $(2,0) * (161, 72)^n$ va a satisfacer la condición de que $ X \equiv 2 \pmod{5}$ (desde $ p \equiv 2, r \equiv 1 , pq+5rs \equiv 2 \pmod{5}$), y por lo tanto, hemos terminado.

---

Nota: Si $(9,2)^2$ no trabajó, ver el $(9,2)^3$. Tenemos la garantía de que algún poder eventualmente de trabajo, ya que tenemos una semilla que funciona.

Desde aquí, usted puede volver atrás y obtener todas las soluciones para $m, n$ si desea hacerlo. Hemos clasificado todas las soluciones, y no sólo a aquellos que están dentro de una familia particular.