Alternando la suma de los restos de

Question

Hay una buena manera de evaluar los siguientes arbitrarias de enteros positivos $n,j,L$:

$$\sum_{k=1}^{\left[\frac{n-L}{j}\right]}(-1)^{(n-kj)\pmod L}$$

Me siento como este debe ser fácil, pero, me confundo pensando en los distintos casos, en particular el mayor-común de los divisores de cada par de los tres índices.

Answer 1

Para simplificar los cálculos y el espacio en el procedimiento escritos vamos a utilizar la siguiente representación de un reducido número natural x modulo L:

$$x \text{ mod L}=x-\text{L}\lfloor \frac{x}{L}\rfloor$$

Además vamos a denotar su suma con la letra $S$ como una función de tres variables $n,j,L$

---

Para empezar vamos a emplear las simplificaciones a las que acabamos de mencionar.

$$S_n(j,L)=\sum_{k=1}^{\lfloor{\frac{n-L}{j}}\rfloor}(-1)^{(n-kj)\pmod L}=\sum_{k=1}^{\lfloor{\frac{n-L}{j}}\rfloor}(-1)^{(n-kj)-\text{L}\lfloor \frac{(n-kj)}{L}\rfloor}$$ $$=\sum_{k=1}^{\lfloor{\frac{n-L}{j}}\rfloor}(-1)^{n+kj+\text{L}\lfloor \frac{n-kj}{L}\rfloor}=(-1)^n\sum_{k=1}^{\lfloor{\frac{n-L}{j}}\rfloor}(-1)^{kj+\text{L}\lfloor \frac{n-kj}{L}\rfloor}$$

Ahora vamos a calcular esta última suma parcial explícitamente para varios casos especiales que se puede evaluar más fácilmente. Después de esto vamos a utilizar en estos casos especiales a volver y construir una fórmula general para el conjunto de la expresión en toda su totalidad.

Caso $1$: $j$ incluso & $L$ incluso $\implies$ $S_n(j,L)=(-1)^n\lfloor{\frac{n-L}{j}}\rfloor$

Caso $2$: $j$ odd & $L$ incluso $\implies$ $S_n(j,L)=(-1)^n\frac{(-1)^{\lfloor{\frac{n-L}{j}}\rfloor}-1}{2}$

Caso $3$: $j$ incluso & $L$ impar $\implies$ $S_n(j,L)=(-1)^n\sum_{k=1}^{\lfloor{\frac{n-L}{j}}\rfloor}(-1)^{\lfloor \frac{n-kj}{L}\rfloor}$

Caso $4$: $j$ odd & $L$ impar $\implies$ $S_n(j,L)=(-1)^n\sum_{k=1}^{\lfloor{\frac{n-L}{j}}\rfloor}(-1)^{k+\lfloor \frac{n-kj}{L}\rfloor}$

---

Ahora bien, si tomamos nota de la idempotence de la función del suelo podemos ver que:

$$\lfloor \frac{n-(\lfloor{\frac{n-L}{j}}\rfloor-k)j}{L}\rfloor=\lfloor \frac{n-(\frac{n-L}{j}-k)j}{L}\rfloor=\lfloor \frac{n-(n-L-kj)}{L}\rfloor=1+\lfloor \frac{kj}{L}\rfloor$$

---

Con esto en conjunto con la simplificación de los casos de $3$ $4$ le da:

$$\text{Case }3: (-1)^n\sum_{k=0}^{\lfloor{\frac{n-L}{j}}\rfloor-1}(-1)^{\lfloor \frac{n-(\lfloor{\frac{n-L}{j}}\rfloor-k)j}{L}\rfloor}=(-1)^{n-1}\sum_{k=0}^{\lfloor{\frac{n-L}{j}}\rfloor-1}(-1)^{\lfloor \frac{kj}{L}\rfloor}$$

$$\text{Case }4: (-1)^n\sum_{k=0}^{\lfloor{\frac{n-L}{j}}\rfloor-1}(-1)^{\lfloor{\frac{n-L}{j}}\rfloor-k+\lfloor \frac{n-(\lfloor{\frac{n-L}{j}}\rfloor-k)j}{L}\rfloor}=(-1)^{\lfloor{\frac{n-L}{j}}\rfloor+n-1}\sum_{k=0}^{\lfloor{\frac{n-L}{j}}\rfloor-1}(-1)^{k+\lfloor \frac{kj}{L}\rfloor}$$

Y ahora romper las sumas parciales hasta en completos sistemas de residuos modulo $L$, además de la utilización de los mencionados anteriormente hecho acerca de la idempotence de la función del suelo nos da que:

$$\lfloor{\frac{(\lfloor{\frac{n-L}{j}}\rfloor-1)-i}{L}}\rfloor=\lfloor{\frac{\frac{n-L}{j}-1-i}{L}}\rfloor=\lfloor{\frac{n-L}{jL}-\frac{1+i}{L}}\rfloor$$

$$\text{Case }3: (-1)^{n-1}\sum_{k=0}^{\lfloor{\frac{n-L}{j}}\rfloor-1}(-1)^{\lfloor \frac{kj}{L}\rfloor}=(-1)^{n-1}\sum_{i=0}^{L-1}\sum_{k=0}^{\lfloor{\frac{n-L}{jL}-\frac{1+i}{L}}\rfloor}(-1)^{\lfloor \frac{(Lk+i)j}{L}\rfloor}$$ $$=(-1)^{n-1}\sum_{i=0}^{L-1}\sum_{k=0}^{\lfloor{\frac{n-L}{jL}-\frac{1+i}{L}}\rfloor}(-1)^{\lfloor \frac{ij}{L}\rfloor}=(-1)^{n-1}\sum_{i=0}^{L-1}(-1)^{\lfloor \frac{ij}{L}\rfloor}\lfloor{\frac{n-L}{jL}-\frac{1+i}{L}}+1\rfloor$$ $$=(-1)^{n-1}\sum_{k=1}^L(-1)^{\lfloor{\frac{(k-1)j}{L}}\rfloor}\lfloor\frac{n-L}{jL}-\frac{k}{L}+1\rfloor$$

También

$$\text{Case }4: (-1)^{\lfloor{\frac{n-L}{j}}\rfloor+n-1}\sum_{k=0}^{\lfloor{\frac{n-L}{j}}\rfloor-1}(-1)^{k+\lfloor \frac{kj}{L}\rfloor}=(-1)^{\lfloor{\frac{n-L}{j}}\rfloor+n-1}\sum_{i=0}^{L-1}\sum_{k=0}^{\lfloor{\frac{n-L}{jL}-\frac{1+i}{L}}\rfloor}(-1)^{Lk+i+\lfloor \frac{(Lk+i)j}{L}\rfloor}$$ $$=(-1)^{\lfloor{\frac{n-L}{j}}\rfloor+n-1}\sum_{i=0}^{L-1}\sum_{k=0}^{\lfloor{\frac{n-L}{jL}-\frac{1+i}{L}}\rfloor}(-1)^{i+\lfloor \frac{ij}{L}\rfloor}=(-1)^{\lfloor{\frac{n-L}{j}}\rfloor+n-1}\sum_{i=0}^{L-1}(-1)^{i+\lfloor \frac{ij}{L}\rfloor}\lfloor{\frac{n-L}{jL}-\frac{1+i}{L}}+1\rfloor=(-1)^{n+\lfloor{\frac{n-L}{j}}\rfloor}\sum_{k=1}^L(-1)^{k+\lfloor{\frac{(k-1)j}{L}}\rfloor}\lfloor\frac{n-L}{jL}-\frac{k}{L}+1\rfloor$$

---

Así que ahora tenemos para $S_n(j,L)$:

Caso $1$: $j$ incluso & $L$ incluso $=(-1)^n\lfloor{\frac{n-L}{j}}\rfloor$

Caso $2$: $j$ odd & $L$ incluso $=(-1)^n\frac{(-1)^{\lfloor{\frac{n-L}{j}}\rfloor}-1}{2}$

Caso $3$: $j$ incluso & $L$ extraño $=(-1)^{n-1}\sum_{k=1}^L(-1)^{\lfloor{\frac{(k-1)j}{L}}\rfloor}\lfloor\frac{n-L}{jL}-\frac{k}{L}+1\rfloor$

Caso $4$: $j$ odd & $L$ extraño $=(-1)^{n+\lfloor{\frac{n-L}{j}}\rfloor}\sum_{k=1}^L(-1)^{k+\lfloor{\frac{(k-1)j}{L}}\rfloor}\lfloor\frac{n-L}{jL}-\frac{k}{L}+1\rfloor$

---

Ahora vamos a adoptar de Kenneth Iverson soporte de la notación para representar funciones de los indicadores, mientras que al mismo tiempo también toma nota de que mediante su anotación tenemos que si $a$ $b$ fórmula lógica y $\wedge$ denota la conjunción lógica operador, entonces tenemos que $[a\wedge b]=[a]\times[b]$.

Así que a partir de esto podemos ver que:

[ES el Caso de $1$] = [$j$ incluso $\wedge$ $L$ incluso] = [$j$ incluso]$\times$[$L$ incluso] = $\frac{(1+(-1)^j)(1+(-1)^L)}{4}$

[ES el Caso de $2$] = [$j$ extraño $\wedge$ $L$ incluso] = [$j$ impar]$\times$[$L$ incluso] = $\frac{(1-(-1)^j)(1+(-1)^L)}{4}$

[ES el Caso de $3$] = [$j$ incluso $\wedge$ $L$ impar] = [$j$ incluso]$\times$[$L$ impar] = $\frac{(1+(-1)^j)(1-(-1)^L)}{4}$

[ES el Caso de $4$] = [$j$ extraño $\wedge$ $L$ impar] = [$j$ impar]$\times$[$L$ impar] = $\frac{(1-(-1)^j)(1-(-1)^L)}{4}$

Donde las expresiones al final seguir a partir de estas igualdades entre las funciones de los indicadores:

$[n \text{ even}]=\frac{1+(-1)^{n}}{2}$ $\text{ and }$ $[n \text{ odd}]=\frac{1-(-1)^{n}}{2}$

---

Ahora, tras la ponderación de cada uno de los cuatro casos de forma adecuada con sus correspondientes funciones de los indicadores y, posteriormente, sumando a todos, ay por fin, llegamos a la siguiente fórmula:

$$\sum_{k=1}^{\lfloor{\frac{n-L}{j}}\rfloor}(-1)^{(n-kj)\pmod L}=\frac{(-1)^n(1+(-1)^j)(1+(-1)^L)}{4}\lfloor{\frac{n-L}{j}}\rfloor$$ $$+\frac{(-1)^n(1-(-1)^j)(1+(-1)^L)((-1)^{\lfloor{\frac{n-L}{j}}\rfloor}-1)}{8}$$

$$-\frac{(-1)^{n}(1+(-1)^j)(1-(-1)^L)}{4}\sum_{k=1}^L(-1)^{\lfloor{\frac{(k-1)j}{L}}\rfloor}\lfloor\frac{n-L}{jL}-\frac{k}{L}+1\rfloor$$

$$+\frac{(-1)^{n+\lfloor{\frac{n-L}{j}}\rfloor}(1-(-1)^j)(1-(-1)^L)}{4}\sum_{k=1}^L(-1)^{k+\lfloor{\frac{(k-1)j}{L}}\rfloor}\lfloor\frac{n-L}{jL}-\frac{k}{L}+1\rfloor$$