¿Cómo puedo resolver esta ecuación de la función?

Question

Dado un número entero positivo $n$ , defina $f(0, j) = f(i, 0) = 0$ , $f(1, 1) = n$ y

$$f(i, j) = \left\lfloor\frac{f(i 1, j)}{2}\right\rfloor + \left\lfloor\frac{f(i, j 1)}{2}\right\rfloor$$ para todos los enteros $i, j 0, (i, j) \neq (1, 1)$ .

¿Cuántos pares ordenados de enteros positivos $(i, j)$ están ahí para que $f(i, j)$ ¿es un número impar?

Answer 1

Llamemos a la respuesta $A$ . Este es el número de valores impar de $f(i,j)$ . Claramente $$A = \sum_{i,j=1}^{\infty} \Bigl(f(i,j) \;\mathrm{mod}\; 2\Bigr)\, .$$ (Obsérvese que los valores de $f(i,j)$ con $i=0$ o $j=0$ no importa, porque todos son 0). Además, define la suma sobre todo valores de $f(i,j)$ como $$S \equiv \sum_{i,j=1}^{\infty} f(i,j)\, .$$ Ahora, para cualquier número entero $m$ tenemos $$m \;\mathrm{mod}\; 2 = m - 2\left\lfloor \frac{m}{2} \right\rfloor\, ,$$ así que $$\begin{align} A &= \sum_{i,j=1}^{\infty} \Bigl(f(i,j) \;\mathrm{mod}\; 2\Bigr)\\ &= \sum_{i,j=1}^{\infty} \left(f(i,j) - 2\left\lfloor \frac{f(i,j)}{2} \right\rfloor \right)\\ &= S \;-\; 2\sum_{i,j=1}^{\infty}\left\lfloor \frac{f(i,j)}{2} \right\rfloor \qquad\qquad (1) \end{align}$$

La suma $S$ puede escribirse como $$\begin{align} S &= \sum_{i,j=1}^{\infty} f(i,j)\\ &= n \;+\; \sum_{i,j=1}^{\infty} \left(\left\lfloor\frac{f(i-1,j)}{2}\right\rfloor \;+\; \left\lfloor\frac{f(i,j-1)}{2}\right\rfloor\right)\\ &= n \;+\; 2\sum_{i,j=1}^{\infty} \left\lfloor\frac{f(i-1,j)}{2}\right\rfloor\\ &= n \;+\; 2\sum_{i,j=1}^{\infty} \left\lfloor\frac{f(i,j)}{2}\right\rfloor\qquad\qquad\qquad(2) \end{align}$$ Al llegar a la segunda línea anterior, hemos utilizado la relación de recursión dada para $(i,j)\ne(1,1)$ así como los hechos que $f(1,1) = n$ y $$\left\lfloor\frac{f(0,j)}{2}\right\rfloor \;+\; \left\lfloor\frac{f(i,0)}{2}\right\rfloor = 0\, .$$ Para llegar a la tercera línea anterior, hemos utilizado el hecho de que por simetría $f(i,j) = f(j,i)$ lo que implica que $$\sum_{i,j=1}^{\infty} \left\lfloor\frac{f(i-1,j)}{2}\right\rfloor \;=\; \sum_{i,j=1}^{\infty} \left\lfloor\frac{f(i,j-1)}{2}\right\rfloor\, .$$ La cuarta línea también se deduce del hecho de que $f(0,j) = 0$ .

Finalmente, si combinamos las ecuaciones (1) y (2) para eliminar la suma restante, llegamos inmediatamente a $A = n$ .