Seja $S(x)=\sum_{m=0}^{\infty}x^m$. Defina, ainda, $P(x)=S(x)^k$. Veja que o coeficiente $c_n$ de $x^n$ em $P(x)$ é exatamente o número que queremos pois é a quantidade de formas que os expoentes de $x$ no produtório dos $S(x)$ por eles mesmos em $P(x)$ somaram juntos $n$. Porém, veja que podemos ver $S(x)$ como um somatório infinito de uma p.g, que é definido para $\mid x\mid<1$ (veja que isso não faz diferença no que estamos calculando). Assim:

$S(x)=\dfrac{1}{1-x}=(1-x)^{-1}$

$\Rightarrow P(x)=(1-x)^{-k}=\sum_{m=0}^{\infty}{-k\choose m}(-x)^m=$

$=\sum_{m=0}^{\infty}{m+k-1\choose m}(-1)^m\cdot(-1)^mx^m={m+k-1\choose m}x^m$

onde na penúlitma igualdade usamos o lema da negação superior.

Assim, temos que $c_n={n+k-1\choose n}$, que é a resposta para o nosso problema. $\blacksquare$

Veja que temos:

$\begin{equation}\begin{cases}a_1-2a_0=3\\a_2-2a_1=3^2\\ \vdots\end{cases}\end{equation}$

Multiplicando a $k$-ésima equação por $x^k$, ficamos com:

$\begin{equation}\begin{cases}a_1x-2a_0x=3x\\a_2x^2-2a_1x^2=3^2x^2\\ \vdots\end{cases}\end{equation}$

E somando tudo:

$\sum_{i\geq1}a_ix^i-\sum_{i\geq0}2a_ix^{i+1}=\sum_{i\geq1}(3x)^i$

Defina por $f(x)=a_0+a_1x+a_2x^2+\dots$ a função geratriz da sequência gerada pela recorrência do enunciado. Assim:

$f(x)-a_0-2xf(x)=\sum_{i\geq0}(3x)^i-1$

$\Rightarrow f(x)-2xf(x)=\sum_{i\geq0}(3x)^i$

$\Rightarrow f(x)=\dfrac{1}{1-2x}=(1-2x)^{-1}\sum_{i\geq0}(3x)^i$

Expandindo o binômio:

$f(x)=\left(\sum_{i\geq0}{-1\choose i}(-1)^i(2x)^i\right)\sum_{i\geq0}(3x)^i$

$\Rightarrow f(x)=\sum_{i\geq0}2^ix^i\sum_{i\geq0}3^ix^i$

 Assim, queremos achar o coeficiente de $x^n$, isto é, o $a_n$. Veja que podemos calculá-lo da seguinte forma:

$a_n=\sum_{k=0}^n2^k3^{n-k}=3^n\sum_{k=0}^n2^k3^{-k}=3^n\sum_{k=0}^n\left(\dfrac{2}{3}\right)^k=3^{n+1}-2^{n+1}$

que é a resposta para o nosso problema. $\blacksquare$

Veja que:

$\begin{equation}\begin{cases}F_2=F_1+F_0\\F_3=F_2+F_1\\ \vdots\end{cases}\end{equation}$

E que, se multiplicamos a $k$-ésima equação por $x^k$ e somamos tudo, temos:

$\sum_{i\geq2}F_ix^{i-1}=\sum_{i\geq1}F_ix^i+\sum_{i\geq0}F_ix^{i+1}$

Definindo por $f(x)$ a função geratriz da recorrência do enunciado. i.e, $f(x)=F_0+F_1x+F_2x^2+\dots$, temos que:

$\dfrac{f(x)-F_1x-F_0}{x}=(f(x)-F_0)+xf(x)\Rightarrow\dfrac{f(x)}{x}-f(x)-xf(x)=1$

$f(x)=\dfrac{x}{1-x-x^2}$

Agora que temos a fórmula fechada para a nossa série, seria muito interessante se conseguíssemos fatorar $1-x-x^2$ em dois produtos da forma $1-x-x^2=-(A+x)(B+x)$, pois daí conseguiriamos usar o Teorema do Binômio para achar nosso $F_n$. Se olhamos as raízes de $(1-x-x^2)$, encontramos que estas são $-\phi$ e $-\bar\phi$ e logo podemos fatorar o polinômio como $-(x+\phi)(x+\bar\phi)$. Assim, usando o Teorema do Binômio, temos que:

$f(x)=-x(x+\phi)^{-1}(x+\bar\phi)^{-1}=$

$=-x\sum_{k\geq0}{-1\choose k}\phi^{-1-k}x^k\cdot\sum_{k\geq0}{-1\choose k}\bar\phi^{-1-k}x^k=$

$=-x\sum_{k\geq0}(-1)^k\phi^{-1-k}x^k\cdot\sum_{k\geq0}(-1)^k\bar\phi^{-1-k}x^k=x\sum_{k\geq0}(-1)^{k}\phi^{-1-k}x^{k}\cdot\sum_{k\geq0}(-1)^{k+1}\bar\phi^{-1-k}x^k$

Porém, é fato que $\dfrac{1}{\bar\phi}=-\phi$, e logo:

$f(x)=\sum_{k\geq0}(-1)^{k}\overline\phi^{k+1}(-1)^{k+1}x^{k}\cdot\sum_{k\geq0}(-1)^{k+1}\phi^{k+1}(-1)^{k+1}x^k$

$\Rightarrow f(x)=x\sum_{k\geq0}-\bar\phi^{k+1}x^k\cdot\sum_{k\geq0}\phi^{k+1}x^k$

$\Rightarrow \dfrac{f(x)}{x}=-\sum_{k\geq0}\bar\phi^{k+1}x^k\cdot\sum_{k\geq0}\phi^{k+1}x^k$

Veja que, como $F_0=0$, podemos considerar $f(x)=F_1x+F_2x^2+\dots$ sem nenhuma alteração nas contas. Assim, $\dfrac{f(x)}{x}=F_1+F_2x+F_3x^2+\dots$, e logo para acharmos o $F_n$, queremos o coeficiente de $x^{n-1}$. Assim, podemos calculá-lo por:

$F_n=-\sum_{k=0}^{n-1}\bar\phi^{k+1}\phi^{n-k}=-\bar\phi^{n+1}\sum_{k=0}^{n-1}\phi^{n-k}\bar\phi^{k-n}=$

$=-\bar\phi^{n+1}\sum_{k=0}^{n-1}\left(\dfrac{\phi}{\bar\phi}\right)^{n-k}=-\bar\phi^{n+1}\left(\dfrac{\left(\dfrac{\phi}{\bar\phi}\right)\left(\left(\dfrac{\phi}{\bar\phi}\right)^{n}-1\right)}{\dfrac{\phi}{\bar\phi}-1}\right)$

Vendo que $\dfrac{\phi}{\overline\phi}=-\phi^2$:

$F_n=\dfrac{\phi^{n+2}\bar\phi-\bar\phi^{n+1}\phi^2}{-\phi^2-1}=\left(\dfrac{\phi^2\bar\phi}{-\phi^2-1}\right)\left(\phi^n-\bar\phi^n\right)=$

$=\dfrac{\phi}{\phi^2+1}\left(\phi^n-\bar\phi^n\right)=\dfrac{1}{\sqrt{5}}\left(\phi^n-\bar\phi^n\right)$ $\blacksquare$

Seja $F(x)=\sum_{n \ge 0}L_nx^n$.

Então,

$F(x)=2+x+\sum_{n \ge 2}(L_{n-1}+L_{n-2})x^n$

$\implies F(x)=2+x+\sum_{n \ge 1}L_nx^{n+1}+\sum_{n \ge 0}L_nx^{n+2}$

$\implies F(x)=2+x+x(\sum_{n \ge 0}L_nx^n-2)+x^2(\sum_{n \ge 0}L_nx^n)$

$\implies F(x)=2+x+x(F(x)-2)+x^2F(x)$

$\implies F(x)=\frac{2-x}{1-x-x^2}$

Note que, sendo $\phi=\frac{1-\sqrt{5}}{2}$ e $\bar{\phi}=\frac{1+\sqrt{5}}{2}$, então $(1-x\phi)(1-x\bar{\phi})=1-x-x^2$. Procuraremos, então, $A$ e $B$ tais que

$F(x)=\frac{2-x}{1-x-x^2}=\frac{A}{(1-x\phi)}+\frac{B}{(1-x\bar{\phi})}$

$\iff A(1-x\bar{\phi})+B(1-x\phi)=2-x$

$\iff A+B + x(-A\bar{\phi}-B\phi)=2-x$

Resolvendo o sistema, obtemos $A=B=1$. Então,

$F(x)=\frac{2-x}{1-x-x^2}=\frac{1}{(1-x\phi)}+\frac{1}{(1-x\bar{\phi})}$

$\implies F(x)=\sum_{n \ge 0}{\phi}^nx^n+\sum_{n \ge 0}{\bar{\phi}}^nx^n$

$\implies F(x)=\sum_{n \ge 0}({\phi}^n+{\bar{\phi}}^n)x^n$

$\implies L_n={\phi}^n+{\bar{\phi}}^n$,

concluindo o problema. $\blacksquare$

Veja que para pensar nisso de forma combinatórica, vamos olhar para a expressão como:

$\dfrac{2(1+2+\dots+(n-1))+n}{n^2}=1$

sendo algo como a soma das probabilidades de certos eventos ocorrerem dentro $n^2$ possíveis. Veja que o $n^2$ lembra a forma de, de forma ordenada, escolhermos dois números entre $1$ e $n$. Isso lembra bastante, pensando dessa forma, as possíveis combinações de dois dados de $n$ faces. Já olhando para o numerador, vemos que temos uma soma de $2n-1$ números que o total de resultados possíveis ao somar dois números de $1$ a $n$ (qualquer valor de $2$ a $2n$). Isso já nos da bastante indício de uma possível solução:

Para provar tal expressão, vamos calcular qual a probabilidade de, jogando dois dados de $n$ faces, em ordem, a soma dos números sorteados ser $k$. Antes de calcular tal probabilidade vamos, primeiramente, ver de quantas formas o número $k$ pode aparecer como soma dos números sorteados no dado. Seja $P(x)=x+x^2+\dots+x^n$. Veja que isso é o mesmo que encontrar o coeficiente de $x^k$ em $P(x)^2$. Assim:

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

$=x^2(x^{2n}-2x^n+1)\sum_{i\geq0}{-2\choose i}(-x)^i=x^2(x^{2n}-2x^n+1)\sum_{i\geq0}(k+1)x^k=$

$=\sum_{i\geq0}(i+1)x^{i+2n+2}-2\sum_{i\geq0}(i+1)x^{i+n+2}+\sum_{i\geq0}(i+1)x^{i+2}$

Veja que o primeiro somatório tem apenas expoentes de $x$ maiores ou iguais que $2n+2$. Porém, a soma máxima dos dados é $2n$, e logo a probabilidade de qualquer $k>2n$ cair é $0$ (lembre-se que mesmo transformando um problema combinatórico em algébrico, pensamentos não-tão-algébricos podem nos poupar bastante tempo).  Assim, podemos ignorar esse somatório para achar o coeficiente de $x^k$. Além disso, veja que o segundo somatório tem expoentes de $x$ maiores ou iguais a $n+2$ e logo devemos olhar dois casos para calcular $[x^k]$, i.e, o coeficiente de $x^k$ em $P(x)^2$:

$i.$ Se $k\leq n+1$: Temos que:

 $[x^k]=k-1$

$i.$ Se $k\geq n+2$: Temos que:

$[x^k]=k-1-2(k-n-1)=2n-k+1$

Ainda, veja que é impossível obter $k\leq1$. Assim, temos que, sendo $p(k)$ a probabilidade do número $k$ ser a soma sorteada:

$p(k)=\begin{equation}\begin{cases}0\text{ se }k\leq1\text{ ou }k>2n\\ \dfrac{k-1}{n^2}\text{ se }2\leq k\leq n+1\\ \dfrac{2n-k+1}{n^2}\text{ se }n+2\leq k\leq2n\end{cases}\end{equation}$

Tá, mas o que tudo isso tem a ver com o que João quer calcular? Veja que, como olhamos todos os resultados possíveis dessas somas, a soma das probabilidades deve ser $1$, que é a probabilidade de algum número ser a resposta da soma dos números sorteados, que é sempre verdade. Assim:

$\sum_{k=2}^{2n}p(k)=1$

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

$\Rightarrow2(1+2+\dots+(n-1))+n=n^2.$ $\blacksquare$

Temos que:

$P(2)=a_0+2\cdot a_1+2^2\cdot a_2+\dots+2^k\cdot a_k+\dots=n$

Defina $f_r(x)=1+x^{2^r}+x^{2^{r+1}}+x^{3\cdot2^r}$. Ainda, defina:

$Q(x)=\prod_{r=0}^{\infty}f_r(x)$

Veja que o coeficiente de $x^n$ é exatamente a resposta para o nosso problema (obs: O produtório não precisa ser infinito, apenas até o momento onde os expoentes de $x$ são imediatamente maiores que $n$, i.e, até $r=\lceil log_2n\rceil$. Porém, olhando isso como um produtório infinito, usamos o Teorema do Binômio ao nosso favor, forçando o aparecimento de séries infinitas, além de ajudar a cancelar muitas coisas). Assim, podemos reescrever $f_r(x)$ como:

$f_r(x)=\dfrac{x^{2^{r+2}}-1}{x^{2^r}-1}$

$\Rightarrow Q(x)=\prod_{r=0}^{\infty}\dfrac{x^{2^{r+2}}-1}{x^{2^r}-1}$

e telescopando:

$Q(x)=\dfrac{1}{x-1}\cdot\dfrac{1}{x^2-1}=(1-x)^{-2}\cdot(1+x)^{-1}$

Usando o Teorema de Binômio:

$Q(x)=\left(\sum_{k=0}^{\infty}{-2\choose k}(-x)^k\right)\left(\sum_{k=0}^{\infty}{-1\choose k}x^k\right)$

Para terminar os cálculos, vamos usar o lema da negação superior:

$Q(x)=\left(\sum_{k=0}^{\infty}{k+1\choose k}(-1)^k\cdot(-1)^kx^k\right)\left(\sum_{k=0}^{\infty}{k\choose k}(-1)^kx^k\right)$

$\Rightarrow Q(x)=\left(\sum_{k=0}^{\infty}(k+1)x^k\right)\left(\sum_{k=0}^{\infty}(-1)^kx^k\right)$

Agora que temos algo com um cara "bonita", vamos calcular o coeficiente de $x^n$. Seja $c_n$ tal coeficiente. Assim:

$c_n=\sum_{k=0}^n(k+1)(-1)^{n-k}$

Se $n$ é par:

$c_n=\sum_{k=0}^n(k+1)(-1)^{n-k}=(1-2)+(3-4)+\dots+((n-2)-(n-1))+n=n-\dfrac{n-2}{2}=\dfrac{n+2}{2}$

Se $n$ é ímpar:

$c_n=\sum_{k=0}^n(k+1)(-1)^{n-k}=(-1+2)+(-3+4)+\dots+(-(n-1)+n)=\dfrac{n+1}{2}$

 Assim, em geral, o coeficiente $c_n=\left\lceil\dfrac{n+1}{2}\right\rceil$. $\blacksquare$

Seja $C(x)=\sum_{n \ge 0}c_nx^n$.

Lembre-se do que vimos sobre convoluções. Temos que

$[C(x)]^2=\sum_{n \ge 0}\sum_{i=0}^{n-1}c_ic_{n-1-}x^n$
$\implies [C(x)]^2=\sum_{n \ge 0}c_{n+1}x^n$
$\implies x[C(x)]^2=\sum_{n \ge 1}c_{n}x^n \implies x[C(x)]^2+1=\sum_{n \ge 0}c_nx^n\implies x[C(x)]^2+1=C(x)$
$\implies x[C(x)]^2-C(x)+1=0$
$\implies C(x)=\frac{1\pm\sqrt{1-4x}}{2x}$

Para escolhermos o sinal, observemos que $C(0)=c_0=1$. Note, ainda, que:

$\lim_{x\to0}C(x)=\lim_{x\to0}c_0+\lim_{x\to0}\sum_{k\geq1}c_kx^k=$

$=c_0+\lim_{x\to0}x\sum_{k\geq1}c_kx^{k-1}=c_0=1$

o que implica que $C(x)$ é contínua em $x=0$. Porém, veja que se o sinal fosse $+$, teriamos que:

$\lim_{x\to0^+}\dfrac{1+\sqrt{1-4x}}{2x}=\dfrac{1}{2}\lim_{x\to0^+}\dfrac{1+\sqrt{1-4x}}{x}\cdot\dfrac{1-\sqrt{1-4x}}{1-\sqrt{1-4x}}=$

$=\dfrac{1}{2}\lim_{x\to0^+}\dfrac{1-1+4x}{x(1-\sqrt{1-4x})}=\dfrac{1}{2}\lim_{x\to0^+}\dfrac{4}{1-\sqrt{1-4x}}=+\infty$, absurdo!

Logo, o sinal deve ser $-$. De fato:

$\lim_{x\to0}\dfrac{1-\sqrt{1-4x}}{2x}=\dfrac{1}{2}\lim_{x\to0}\dfrac{1-\sqrt{1-4x}}{x}\cdot\dfrac{1+\sqrt{1-4x}}{1+\sqrt{1-4x}}=$

$=\dfrac{1}{2}\lim_{x\to0}\dfrac{4x}{x(1+\sqrt{1-4x})}=\dfrac{1}{2}\lim_{x\to0}\dfrac{4}{1+\sqrt{1-4x}}=1$, como queriamos.

Portanto, o sinal adotado é o negativo.

Calculemos, então, $(1-4x)^{\frac{1}{2}}$.

Para isso, calcularemos, primeiramente, ${\frac{1}{2} \choose n}$, para $n>0$,

${\frac{1}{2} \choose n}=\frac{(\frac{1}{2})(\frac{1}{2}-1)(\frac{1}{2}-2)\dots(\frac{1}{2}-n+1)}{n!}$
${\frac{1}{2} \choose n}=(\frac{1}{2})(\frac{-1}{2})^{n-1}(\frac{1\cdot3\cdot\dots\cdot(2n-3)}{n!})$
${\frac{1}{2} \choose n}=(\frac{1}{2})(\frac{-1}{2})^{n-1}(\frac{(2n-2)!}{n!\cdot2\cdot4\cdot\dots\cdot(2n-2)})$
${\frac{1}{2} \choose n}=(\frac{1}{2})(\frac{-1}{2})^{n-1}(\frac{(2n-2)!}{2^{n-1}(n-1)!n!})$
${\frac{1}{2} \choose n}=(\frac{1}{2})(\frac{-1}{4})^{n-1}(\frac{(2n-2)!}{(n-1)!n!})$
${\frac{1}{2} \choose n}=(\frac{1}{2n})(\frac{-1}{4})^{n-1}{2n-2\choose n-1}$

Então,

$(1-4x)^{\frac{1}{2}}=\sum_{n\ge0}{\frac{1}{2} \choose n}(-4x)^n$
$(1-4x)^{\frac{1}{2}}=1+\sum_{n\ge1}(\frac{1}{2n})(\frac{-1}{4})^{n-1}{2n-2\choose n-1}(-4x)^n$
$(1-4x)^{\frac{1}{2}}=1-2\sum_{n\ge1}\frac{1}{n}{2n-2 \choose n-1}x^n$

Assim,

$C(x)=\frac{1-\sqrt{1-4x}}{2x}$
$C(x)=\frac{1-(1-2\sum_{n\ge1}\frac{1}{n}{2n-2 \choose n-1}x^n)}{2x}$
$C(x)=\sum_{n\ge1}\frac{1}{n}{2n-2 \choose n-1}x^{n-1}$
$C(x)=\sum_{n\ge0}\frac{1}{n+1}{2n \choose n}x^n$,

o que nos dá $c_n=\frac{1}{n+1}{2n \choose n}$, concluindo o problema. $\blacksquare$

Seja $A(x)=\sum_{n=0}^{\infty}x^{a_n}$, com $x\in[0,1)$.

Notemos que a condição do enunciado é equivalente a

$A(x)A(x^2)A(x^4)=\sum_{n=0}^{\infty}x^n=\frac{1}{1-x}$.

Observemos ainda que, como a sequência é crescente e o $0$ pode ser representado da forma do enunciado, $a_0=0$, então $A(0)=1$.

Plotando $x^2$ como $x$,

$A(x^2)A(x^4)A(x^8)=\frac{1}{1-x^2}$

Logo, $\frac{A(x)}{A(x^8)}=1+x \implies A(x)=A(x^8)(1+x)$ (i)

No geral,

$A(x^{8^i})=A(x^{8^{i+1}})(1+x^{8^i})$ (ii)

Então, usando (ii) em (i) recursivamente, obtemos

$A(x)=\prod_{i=0}^{\infty}(1+x^{8^i})$,

já que $\lim_{n \rightarrow +\infty}A(x^{8^n})=A(0)=1$.

Então, $a_0=0$ e, para $i \ge 1$, $a_i$ é o $i$-ésimo menor número que é a soma de potências de $8$ distintas.

Sejam

$a_i=\sum_{k\ge0}x_k8^{k}$ e $a_j=\sum_{k\ge0}y_k8^{k}$ em que $x_k$,$y_k\in\{0,1\}$.

Seja $C$ o maior inteiro não negativo tal que $x_C \not = y_C$. Ele existe, pois não há termos iguais na sequência e há um momento a partir do qual todos os $x_k$ e $y_k$ são $0$ para um par de $i$ e $j$ fixado. Então, $a_i>a_j \iff x_C=1$ e $y_C=0$. Mas, note que isso é equivalente à condição para

$\sum_{k\ge0}x_k2^{k}>\sum_{k\ge0}y_k2^{k}$.

Como todo número que é a soma de potências de $8$ distintas aparece na sequência, todo inteiro não negativo aparece nas somas $\sum_{k\ge0}x_k2^{k}$, variando $i \ge 0$. Como a sequência é crescente, isso implica que $x_k$ é o $k$-ésimo algarismo do número $i$ na base binária. Em particular, como $1998=2^1+2^2+2^3+2^6+2^7+2^8+2^9+2^{10}$, $a_{1998}=8^1+8^2+8^3+8^6+8^7+8^8+8^9+8^{10}$. $\blacksquare$

Atribuímos à peça $(i,j)$, $i\in\{1,2,\dots, a\}$, $j\in\{1,2,\dots,b\}$, o valor $x^iy^j$.

Então, cada peça $p$ x $1$ tem uma soma

$x^iy^j+x^{i+1}y^j+\dots+x^{i+p-1}y^j=(1+x+\dots+x^{p-1})x^iy^j$.

Analogamente, para uma peça $1$ x $q$, temos uma soma

$(1+y+ \dots + y^{q-1})x^{i'}y^{j'}$.

Então, podemos zerar a soma de cada peça ao tomarmos

$x=cis(\frac{2\pi}{p})$ e $y=cis(\frac{2\pi}{q})$.

E a soma de todas as peças é

$\sum_{1 \le i \le a,1 \le j \le b}x^iy^j =$

$= xy(\sum_{0 \le i \le a-1}x^i)(\sum_{0 \le j \le b-1}y^j) =$

$= xy(\frac{x^a-1}{x-1})(\frac{y^b-1}{y-1})$

Como essa soma é zero, $x^a-1=0$ ou $y^b-1=0$.

No 1º caso, isso implica

$cis(\frac{2\pi}{p})=cis(\frac{2k\pi}{a})$,

para algum $k\in\{0,1,\dots, a-1\}$. Como $0 \le \frac{2\pi}{p}$,$\frac{2k\pi}{a} < 2\pi$, para $p>1$ (no caso $p=1$, temos $1|a$) isso implica

$\frac{2\pi}{p}=\frac{2k\pi}{a}$

$\implies \frac{a}{p}=k$,

um inteiro. O que nos dá $p|a$ nesse caso.

Analogamente, para o 2º caso ($y^b-1=0$), temos $q|b$. Portanto, $p|a$ ou $q|b$, como queríamos. $\blacksquare$

Primeiramente, seja $f(x)=(1+x)(1+x^2)(1+x^3)\dots(1+x^p)=a_0+a_1x+a_2x^2+\dots+a_mx^m$, onde $m={p+1\choose2}$. Veja que queremos calcular $\sum_{p\mid k}a_k$. Para isso, sendo $\omega=cis\left(\dfrac{2\pi}{p}\right)$, calculemos:

$\sum_{k=0}^{p-1}f(\omega^k)$

Lema: $\sum_{k=0}^{p-1}\omega^{qk}=0$ se mdc$(q,p)=1$ e $\sum_{k=0}^{p-1}\omega^{qk}=p$, caso o contrário.

Prova: Se $p\nmid q$, então $\omega^q\neq1$ e logo podemos fatorar $\sum_{k=0}^{p-1}\omega^{qk}$ como:

$=\dfrac{\omega^{qp}-1}{\omega^q-1}=0$ pois $\omega^{qp}=(\omega^p)^q=1$

Se $p\mid q$, então $\omega^{qk}=(\omega^p)^{\dfrac{q}{p}k}=1, \forall k$ entre $0$ e $p-1$. Assim, cada termo do somatório será $1$ e logo, como ele tem $p$ termos:

$\sum_{k=0}^{p-1}\omega^{qk}=\sum_{k=0}^{p-1}1=p$ $\square$

Com o nosso lema provado, e sendo $R$ a quantidade de subconjuntos que queremos:

$\sum_{k=0}^{p-1}f(\omega^k)=\sum_{i=0}^{m}\left(a_i\sum_{k=0}^{p-1}\omega^{ik}\right)=$

$=p\sum_{p\mid i}a_i=pR+p$, onde o $+p$ aparece pois estamos contando com o conjunto vazio.

Assim, agora nada melhor que tentar encontrar o valor de $\sum_{k=0}^{p-1}f(\omega^k)$. Para isso, veja que, se $p\nmid k$:

$f(\omega^k)=(1+\omega^k)(1+\omega^{2k})\dots(1+\omega^{pk})=(1+\omega)(1+\omega^2)\dots(1+\omega^p)=f(\omega)$

pois $\{k,2k,\dots,pk\}=k\{1,2,\dots,p\}$ é um s.c.r$\pmod{p}$, i.e, seus elementos são uma permutação de $\{1,2,\dots,p\}$ módulo $p$, e $\omega$ tem ordem $p$. Além disso, sabemos que $\omega,\omega^2,\dots,\omega^p$ são as raízes de $x^p-1$ e logo:

$x^p-1=(x-\omega)(x-\omega^2)\dots(x-\omega^p)$

Assim, temos que, para $1\leq k\leq p-1$:

$f(\omega^k)=f(\omega)=(1+\omega)(1+\omega^2)\dots(1+\omega^p)=$

$=(-1)^p((-1)-\omega)((-1)-\omega^2)\dots((-1)-\omega^p)=(-1)^p((-1)^p-1)=1+1=2$

Além disso, para $k=0$:

$f(\omega^0)=(1+1)(1+1)\dots(1+1)=2^p$

Assim:

$\sum_{k=0}^{p-1}f(\omega^k)=2^p+\sum_{k=1}^{p-1}f(\omega^k)=2^p+\sum_{k=1}^{p-1}f(\omega)=$

$=2^p+2(p-1)=pR+p$

$\Rightarrow R=\dfrac{2^p+p-2}{p}$

que é o valor que queriamos encontrar. $\blacksquare$

Observação: A ideia de olhar para raízes da unidade é muito forte quando queremos filtrar apenas certos coeficientes que tem índice em p.a. Essa ideia pode ser generalizada pela Fórmula da Multisecção. Fica então como exercício ao leitor:

Ache $\sum_{n\equiv k\pmod{q}}a_nx^n$ em função da função geradora dos $a_i$'s e de $n,k$ e $q$.

Dessa vez faremos algo um pouco diferente. Defina $f(x) = (1+xy)(1+x^2y)(1+x^3y) ... (1+x^{2p}y)$ e $a_{n,k}$ o coeficiente de $x^ny^k$. Além disso, seja $R$ a nossa quantidade desejada.

Oberve que ao expandirmos esse produto, a soma dos coeficientes de $x^{pk} y^{p}$ para todos $k$ possíveis nos dará a resposta do problema. Para filtrarmos, definamos $w= cis(\frac{2\pi}{p})$. Logo:

$\cdot \sum_{k=0}^{p-1}f(w^{k},y)$ é $p\cdot S$ onde $S$ é a soma de todos $a_{i,j}y^j$ em que $i$ é múltiplo de $p$. Mas desejamos os coeficientes que possuam $j$ exatamente igual a $p$ dentre esses.

$\sum_{j=0}^{p-1} \sum _{i=0}^{p-1} f(w^{i},w^{j}) = \sum_{j=0}^{p-1} p \cdot \sum _{p|i, 0\leq j \leq 2p} a_{i,j}y^j = p^2 \sum_{p|i,p|j} a_{i,j}$, porém:

$\sum_{p|i,p|j} a_{i,j} = a_{0,0} + R + a_{1+2+...+2p,2p} = R+2$ pois $a_{0,0}=a_{1+...+2p,2p}=1$. Conclusão:

$\sum_{j=0}^{p-1}\sum_{i=0}^{p-1}f(w^{i},w^{j}) = (R+2)(p^2)$. Para evaluar esse somatório da esquerda, o dividimos em $2$ partes:

• $i$ diferente de 0: $\sum_{j=0}^{p-1}\sum_{i=1}^{p-1}f(w^{i},w^{j})$

Oberve que $(x-w)(x-w^2)(x-w^3)...(x-w^{p})=x^{p}-1$ e por um argumento análogo, trocando $w$ por $w^k$ no produto da esquerda, a igualdade ainda continua valendo pois os fatores giram e no final são os mesmos. Além disso, $(x-w^{p+1})(x-w^{p+2})...(x-w^{2p}) = (x-w)(x-w^2)(x-w^3)...= (x-w^{p})=x^{p}-1$ pois $x-w^{k}=x-w^{p+k}$. Portanto:

$(x-w)(x-w^2)...(x-w^{2p}) = (x^{p}-1)^2$ e ainda vale se trocarmos $w$ por $w^k$ para algum k fixo não múltiplo de $p$. Mas observe que $f(w^i,w^j) = \prod_{k=1}^{2p}(1+w^{ik}w^j) = \prod_{k=1}^{2p}(1+w^{ik+j})=[\prod_{k=1}^{p}(1+w^k)]^2$ pois $ik+j$ percorre cada resíduo $mod p$ exatamente duas vezes quando variamos $k$ de $1$ a $2p$ (por isso supomos nesse caso que i não é múltiplo de p). Assim, temos:$f(w^i,w^j) =((-1)^{p}-1)^2 =4$

$\sum_{j=0}^{p-1}\sum_{i=1}^{p-1}f(w^{i},w^{j}) = 4p(p-1)$

• caso $i=0$, $\sum_{j=0}^{p-1} f(1,w^{j})$:

$\sum_{j=0}^{p-1} f(1,w^{j}) = \sum_{j=0}^{p-1}(1+w^j)^{2p} = \sum_{j=0}^{p-1}\sum_{k=0}^{2p}\binom{2p}{k}w^{jk}$ e note que pros k não múltiplos de $p$, $w^{jk}$ corre todos as raízes da unidade, portanto zerará a parcela. Em outras palavras:

$\sum_{j=0}^{p-1} f(1,w^{j}) = \sum_{k=0,k=p,k=2p} \sum_{j=0}^{p-1}\binom{2p}{k}w^{jk} = p + p\cdot \binom{2p}{p}+p = 2p + p\binom{2p}{p}$.

Fechando o problema, então temos:
$(R+2)p^2 = 4p(p-1)+ (p\binom{2p}{p} + 2p) \Rightarrow (R +2)p^2= p\binom{2p}{p} + 4p^2 - 2p$

$\Rightarrow (R +2)= \frac{\binom{2p}{p}}{p} + 4 - \frac{2}{p}$

$\Rightarrow R = \frac{\binom{2p}{p}}{p} - \frac{2}{p} +2$