Demostrar

Question

Estoy tratando de solucionar este problema del libro Skiena, "Manual de diseño del algoritmo".

No sé la respuesta pero parece que la entidad en el R.H.S. es la suma de la serie $1+2+3+..$. Sin embargo la secuencia en el lado izquierdo es cuadrada de la serie y me parece de la forma:

$-3-7-11-15\ldots $

Me siento como su de la forma cerrada:

$\sum(-4i+1)$

Entonces, ¿cómo pruebo que la igualdad es correcta?

Answer 1

La siguiente prueba sería más de lo necesario, pero ilustra un método general que es útil para problemas similares.

Que $$A(k) = 1^2 - 2^2 + 3^2 - 4^2 + \ldots + (-1)^{k-1} k^2$ $ y $$B(k)=(-1)^{k-1} \cdot \frac{k(k+1)}2.$$ It suffices to prove that $A (0) = B (0) $ and $$A(k)-A(k-1)=B(k)-B(k-1)$% $# %k\ge1 de #%.

Está claro que $ for all $.

$$\begin{align} A(k) - A(k-1) &= (-1)^{k-1} k^2 \ B(k) - B(k-1) &= (-1)^{k-1} \cdot \frac{k(k+1)}2 - (-1)^{k-2} \cdot \frac{(k-1)k}2 \ &= (-1)^{k-1} \left(\frac{k(k+1)}2 + \frac{(k-1)k}2 \right) \ &= (-1)^{k-1} \left(\frac{k^2+k}2 + \frac{k^2-k}2 \right) \ &= (-1)^{k-1} k^2 \end{align} $$

Para completar la prueba, tenga en cuenta que los $A(0)=B(0)=0$, $$\begin{align} A(k) &= A(0) + \sum{i=1}^k (A(i) - A(i-1)) \ &= B(0) + \sum{i=1}^k (B(i) - B(i-1)) \ &= B(k). \end{align} $$

Answer 2

Proceder inductivo. Verifique que $k=1$, $1 = 1$.

Ahora Supongamos que el resultado tiene $n - 1$. Entonces

$$ 1^2 + \dots + (-1)^{n-1} n^2 = 1 + \dots + (-1)^{n-2} (n-1)^2 + (-1)^{n-1} n^2 = (-1)^n \frac{n(n-1)}{2} + (-1)^{n-1} n^2 = (-1)^n \left(\frac{n(n-1)-2n^2}{2} \right) = (-1)^n \left(\frac{-n^2-n}{2} \right) = (-1)^{n-1} \left(\frac{n(n+1)}{2}\right)$$

La hipótesis de inducción se aplicó en la segunda igualdad.

Answer 3

Sugerencia: para mostrar \begin{align*} \sum_{j=0}^k(-1)^{j-1}j^2=(-1)^{k-1}\frac{k(k+1)}{2}\qquad\qquad k\geq 0\tag{1} \end{align*} consideramos que las secuencias de $(a_k)_{k\geq 0}$ y la correspondiente generación de funciones de $\sum_{k=0}^{\infty}a_kx^k$ como bloques de construcción para generar la mano izquierda de la suma en (1). Esto nos permite calcular el lado derecho de (1). \begin{array}{crl} (a_k)_{k\geq 0}\qquad &\qquad A(x)=&\sum_{k=0}^{\infty}a_kx^k\\ \hline\\ ((-1)^{k-1})_{k\geq 0}\qquad&\qquad -\frac{1}{1+x}=&\sum_{k=0}^{\infty}(-1)^{k-1}x^k\\ ((-1)^{k-1} k)_{k\geq 0}\qquad&\qquad -\left(x\frac{d}{dx}\right)\frac{1}{1+x} =&\frac{x}{(1+x)^2}\\ &=&\sum_{k=0}^{\infty}(-1)^{k-1}kx^k\\ ((-1)^{k-1} k^2)_{k\geq 0}\qquad&\qquad -\left(x\frac{d}{dx}\right)^2\frac{1}{1+x} =&\frac{x(1-x)}{(1+x)^3}\\ &=&\sum_{k=0}^{\infty}(-1)^{k-1}k^2x^k\\ (\sum_{j=0}^{k}(-1)^{j-1} j^2)_{k\geq 0}\qquad&\qquad -\frac{1}{1-x}\left(x\frac{d}{dx}\right)^2\frac{1}{1+x} =&\frac{x}{(1+x)^3}\\ &=&\sum_{k=0}^{\infty}\left(\sum_{j=0}^{k}(-1)^{j-1}j^2\right)x^k\tag{2}\\ \end{array}

Podemos ver en la pequeña introducción sobre el operador $x\frac{d}{dx}$ transforma $a_k$ $ka_k$y la multiplicación con $\frac{1}{1-x}$ actúa como operador de suma.

También es conveniente utilizar el coeficiente de operador $[x^n]$ para denotar el coeficiente de $x^n$ en una generación de la serie.

Podemos obtener a partir de (2) por $k\geq 1$

\begin{align*} \sum_{j=0}^{k}(-1)^{j-1}j^2&=[x^k] \frac{-1}{1-x}\left(x\frac{d}{dx}\right)^2\frac{1}{1+x}\\ &=[x^k] \frac{x}{(1+x)^3}\\ &=[x^{k-1}]\sum_{n=0}^{\infty}\binom{-3}{n}x^{n}\tag{3}\\ &=\binom{-3}{k-1}\\ &=(-1)^{k-1}\binom{k+1}{2}\tag{4}\\ &=(-1)^{k-1}\frac{k(k+1)}{2} \end{align*}

Comentario:

• En (3) se utiliza el binomio de la serie de la representación.

• En (4) utilizamos la fórmula $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k$ para los coeficientes binomiales.

Answer 4

Sugerencia: Distinguir los casos donde $n$ es par o impar y uso que $-4i+1=(-2i)+(-2i+1)$

Answer 5

i) $k=2n$:\begin{align} \sum{m=1}^{2n}(-1)^{m-1}m^2&=\sum{m=1}^{2n}m^2-2\sum{m=1}^{n}(2m)^2\ &=\sum{m=1}^{2n}m^2-8\sum{m=1}^{n}m^2\ &=\frac{2n(2n+1)(4n+1)}{6}-8\frac{n(n+1)(2n+1)}{6}\ &=\frac{2n(2n+1)(4n+1-4n-4)}{6}\ &=\frac{2n(2n+1)(-1)}{2}=-\frac{k(k+1)}{2}=(-1)^{k-1}\frac{k(k+1)}{2} \end {Alinee el} ii) $k=2n+1$:\begin{align} \sum{m=1}^{2n+1}(-1)^{m-1}m^2&=(2n+1)^2+\sum_{m=1}^{2n}(-1)^{m-1}m^2\ &=(2n+1)^2+\frac{2n(2n+1)(-1)}{2}\ &=\frac{(2n+1)(4n+2-2n)}{2}=\frac{k(k+1)}{2}=(-1)^{k-1}\frac{k(k+1)}{2} \end {Alinee el}