Funções geratrizes e suas aplicações combinatóricas
Existem muitas formas de realizar contagens em problemas de olimpíada. Funções geratrizes são um jeito eficiente de expressar algebricamente alguma quantia e poder, a partir dela, manipular e obter novos resultados. Digamos que tenhamos uma sequência de naturais: $$a_0$$, $$a_1$$, $$a_2$$, … de reais. Dizemos que a função geratriz associada à sequência é a série formal:
$$f(x)=a_0+a_1x +a_2x^2+\dots = \sum_{k=0}^{\infty}a_ix^i$$.
Para que façamos bom uso dessa técnica, precisamos de certa familiaridade e conhecimento de alguns teoremas e técnicas:
Binômio de Newton generalizado
Geralmente quando falamos de binômio, lembramos sempre da definição usual que aprendemos no colégio de que $${n\choose k}=\dfrac{n!}{k!\cdot(n-k)!}$$, onde $$k$$ e $$n$$ são inteiros não-negativos. Porém, como tratamos de funções geratrizes e queremos uma forma mais geral para isso, teremos agora um nova definição para o binômio, que ainda assim, mantém suas propriedades para $$n$$ e $$k$$ inteiros não negativos. Temos:
$${n\choose k}=\dfrac{n\cdot(n-1)\cdot\dots\cdot(n-k+1)}{k!}=\dfrac{(n)_k}{k!}$$, onde $$n$$ é um complexo qualquer e $$k$$ é um inteiro não-negativo.
(obs: $$(n)_k$$ é a representação do “fatorial em queda”, que funciona de forma semelhante ao fatorial, diminuindo de $$1$$ em $$1$$, k vezes). Temos ainda, um lema muito importante para quando tivermos um número negativo na parte de cima do binômio.
Lema da Negação Superior: $${r\choose k}={k-r-1\choose k}(-1)^k$$
Prova: Exercício ao leitor (basta usar a definição).
Teorema do Binômio Generalizado
Agora que temos uma definição geral para o binômio, nada melhor do que generalizar o Teorema do Binômio, onde $$\mid x\mid>\mid y\mid$$:
$$(x+y)^r=\sum_{k=0}^{\infty}{r\choose k}x^{r-k}y^k$$
Convoluções e Números de Catalan
Observemos que, sendo $$A(x)$$ e $$B(x)$$ funções geratrizes das sequências $$\{a_n\}^{\infty}_{n=0}$$ e $$\{b_n\}^{\infty}_{n=0}$$, respectivamente.
$$A(x)B(x)=\sum_{n=0}^{\infty}(a_0b_n+a_1b_{n-1}+\dots+a_ib_{n-i}+\dots+a_{n-1}b_1+a_nb_0)x^n$$
Em particular, se as sequências são iguais,
$$[A(x)]^2=\sum_{n=0}^{\infty}(a_0a_n+a_1a_{n-1}+\dots+a_{n-1}a_1+a_na_0)x^n$$
um padrão muito interessante para alguns problemas de Combinatória. Em particular, definimos o $$n$$-ésimo número de Catalan como $$c_n$$ tal que $$c_0=1$$ e $$c_{n}=\sum_{i=0}^{n-1}c_ic_{n-1-i}$$, para $$n \ge 1$$. Encontrar a fórmula fechada de $$c_n$$ é um dos problemas propostos. Os números de Catalan aparecem em diversos problemas de Combinatória como:
- a quantidade de modos de dividir um $$(n+2)$$-ágono convexo em $$n$$ triângulos com diagonais desse polígono que não se intersectam;
- o número de caminhos em um grid $$n$$x$$n$$ com $$n^2$$ quadrados unitários passando apenas por lados dos quadrados e caminhando apenas para a direita e para cima, começando do canto inferior esquerdo;
- a quantidade de sequências de $$2n$$ parênteses com $$n$$ abre parênteses e $$n$$ fecha parênteses tal que, considerando uma soma $$S = 0$$, ao percorrermos a sequência da esquerda para a direita, adicionando $$1$$ a cada abre parênteses e subtraindo $$1$$ a cada fecha parênteses, essa soma nunca é negativa.
Abaixo apresentamos alguns exemplos para nos familiarizarmos mais com essas técnicas:
Exemplos: tente fazê-los antes de ler a solução.
Exemplo 1. Defina $$a_n=a_{n-1}+1$$ uma recorrência, com $$a_1=1$$. Ache $$a_n$$ em função de $$n$$.
Solução: Essa recorrência é facilmente resolvível apenas telescopando isso. Mas como estamos treinando funções geratrizes, que tal usa-las? Para isso, faremos o seguinte. Veja que:
$$\begin{equation}\begin{cases}a_2=a_1+1\\a_3=a_2+1\\ \vdots\end{cases}\end{equation}$$
Agora, multiplique a $$i$$-ésima equação por $$x^i$$, de modo que ficamos com:
$$\begin{equation}\begin{cases}a_2x=a_1x+x\\a_3x^2=a_2x^2+x^2\\ \vdots\end{cases}\end{equation}$$
E agora, somando as infinitas equações:
$$\sum_{k=1}^{\infty}a_{k+1}x^{k}=\sum_{k=1}^{\infty}a_kx^k+\sum_{k=1}^{\infty}x^k$$
Agora, defina $$f(x)=a_1x+a_2x^2+\dots$$ a função geratriz da nossa recorrência. Assim:
$$\dfrac{f(x)-a_1x}{x}=f(x)+\dfrac{x}{1-x}$$
$$\Rightarrow\dfrac{f(x)-xf(x)-x}{x}=\dfrac{x}{1-x}$$
$$\Rightarrow\dfrac{f(x)(1-x)}{x}=\dfrac{1}{1-x}$$
$$\Rightarrow f(x)=\dfrac{x}{(1-x)^2}$$
Agora, expandindo $$(1-x)^{-2}$$ com o Teorema do Binômio:
$$f(x)=x\sum_{k=0}^{\infty}{-2\choose k}(-1)^kx^k$$
e agora, usando o lema da negação superior:
$$f(x)=x\sum_{k=0}^{\infty}{k+1\choose k}(-1)^{2k}x^k=x\sum_{k=0}^{\infty}(k+1)x^k=$$
$$=\sum_{k=0}^{\infty}(k+1)x^{k+1}=\sum_{k=1}^{\infty}kx^k$$
Assim, concluimos que o coeficiente de $$x^n$$ é exatamente $$n$$ em $$f(x)$$, ou seja, $$a_n=n$$, e logo nossa recorrência está resolvida. $$\blacksquare$$
Veja que este método pode parecer muito mais trabalhos que apenas telescopar, e nesse caso, de fato é. Porém, estamos diante de uma recorrência bem simples. O uso de funções geratrizes em recorrências mais robustas se mostrará muito poderoso mais futuramente. A ideia de transformar recorrências em somas de funções geradoras consegue resolver boa parte das recorrências definidas que você se dará de cara na sua vida olímpica, com certa facilidade até (Não te garanto que sempre…)! De qualquer maneira, vejamos mais alguns problemas interessantes que podem ser massacrados por funções geratrizes.
Exemplo 2. Vejamos outro exemplo de uso de funções geratrizes para encontrarmos fórmulas fechadas para recorrências.
Seja $$\{a_n\}_{n=0}^{\infty}$$ uma sequência de modo que $$a_0=1$$, $$a_1=3$$ e $$a_{n}=3a_{n-1}-2a_{n-2}$$, para $$n \ge 2$$. Determine a fórmula fechada de $$a_n$$.
Solução: Seja $$A(x)=\sum_{n \ge 0}a_nx^n$$. Então,
$$A(x)=1+3x+\sum_{n \ge 2}a_nx^n$$
Usando a recorrência,
$$\implies A(x)=1+3x+\sum_{n \ge 2}(3a_{n-1}-2a_{n-2})x^n$$
$$\implies A(x)=1+3x+\sum_{n \ge 1}(3a_n)x^{n+1}+\sum_{n \ge 0}(-2a_n)x^{n+2}$$
$$\implies A(x)=1+3x+3x(\sum_{n \ge 0}a_nx^n – 1)-2x^2\sum_{n \ge 0}a_nx^n$$
$$\implies A(x)=1+3x[A(x)]-2x^2[A(x)]$$
$$\implies A(x)= \frac{1}{2x^2-3x+1}$$
Note que $$(x-1)(2x-1)=2x^2-3x+1$$ e podemos obter fórmulas fechadas para $$\frac{1}{x-1}$$ e $$\frac{1}{2x-1}$$, então seria interessante encontrarmos $$U$$ e $$V$$ tais que
$$A(x)= \frac{1}{2x^2-3x+1}=\frac{U}{x-1}+\frac{V}{2x-1}$$
$$\iff U(2x-1)+V(x-1)=1$$
$$\iff x(2U+V)-U-V=1$$
Resolvendo o sistema, obtemos $$U=1$$ e $$V=-2$$.
Então,
$$A(x)=(\frac{1}{x-1})+(\frac{-2}{2x-1})$$
$$\implies A(x)=-(\frac{1}{1-x})+2(\frac{1}{1-2x})$$
$$\implies A(x)=-\sum_{n \ge 0}x^n+2\sum_{n \ge 0}2^nx^n$$
$$\implies A(x)=\sum_{n \ge 0}(2^{n+1}-1)x^n$$
Portanto, $$a_n=2^{n+1}-1$$. $$\blacksquare$$
Exemplo 3. (Identidade de Vandermonde) Prove que
$${a+b\choose k} = \sum_{i=0}^k {a\choose i}{b \choose k-i}$$
Solução: Temos que
$$(1+x)^{a+b}=(1+x)^a(1+x)^b$$
Então, pelo teorema do binômio,
$$\sum_{k=0}^{\infty}{a+b\choose k}x^k=\sum_{k=0}^{\infty}\sum_{i=0}^k{a\choose i}{b\choose k-i}x^k$$
E, comparando os coeficientes de $$x^k$$,
$${a+b\choose k} = \sum_{i=0}^k {a\choose i}{b \choose k-i}$$
como queríamos. $$\blacksquare$$
Problemas:
Problema 1. (Combinação completa) Sejam $$a_1,a_2,\dots,a_k$$ inteiros não-negativos. Encontre o número de k-tuplas $$(a_1,a_2,\dots,a_k)$$ tais que:
$$a_1+a_2+\dots+a_k=n$$
onde $$n\in\mathbb{Z}_{>0}$$.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]
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$$
[/spoiler]
Problema 2. Resolva, em função de $$n$$, a recorrência
$$a_n-2a_{n-1}=3^n$$,
onde $$a_0=1$$.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]
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$$
[/spoiler]
Problema 3. (Sequência de Fibonacci) Encontre $$F_n$$ em função de $$n$$, onde $$F_1=1$$, $$F_0=0$$ e $$F_{n+1}=F_n+F_{n-1}, \forall n\geq2$$.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]
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$$
[/spoiler]
Problema 4. (Números de Lucas) Definimos o $$n$$-ésimo número de Lucas $$L_n$$ como $$L_0=2$$, $$L_1=1$$ e $$L_n=L_{n-1}+L_{n-2}$$ para $$n \ge 2$$. Determine a fórmula fechada para o $$n$$-ésimo número de Lucas.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]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$$[/spoiler]
Problema 5. João quer provar que a seguinte expressão é verdadeira:
$$2(1+2+\dots+(n-1))+n=n^2$$
Porém, ele está cansado de mostrar isso das formas “mais usuais”. Ele quer provar isso usando combinatória e funções geratrizes! Ache uma forma de provar a expressão acima para João usando essas ferramentas.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]
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$$
[/spoiler]
Problema 6. (China-1996) Encontre o número de polinômios $$P(x)$$ com coeficientes em $$\{0,1,2,3\}$$ tais que:
$$P(2)=n$$
onde $$n\in\mathbb{Z}_{>0}$$, em função de $$n$$.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]
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$$
[/spoiler]
Problema 7. Seja $$c_n$$ o $$n$$-ésimo número de Catalan. Determine a função geratriz da sequência dos números de Catalan e a fórmula fechada para $$c_n$$.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]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$$
[/spoiler]
Problema 8. (IMO Shortlist 1998) Seja $$\{a_n\}_{n=0}^{\infty}$$ uma sequência crescente de inteiros não negativos tal que todo inteiro não negativo pode ser escrito de forma única como um $$a_i+2a_j+4a_k$$, em que $$i$$, $$j$$ e $$k$$ não são necessariamente distintos. Determine $$a_{1998}$$.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]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$$ [/spoiler]
Problema 9. Um retângulo $$a$$ × $$b$$ pode ser coberto completamente, sem buracos, excessos ou sobreposições, com peças do tipo $$p$$ × $$1$$ e $$1$$ × $$q$$, sendo $$a$$, $$b$$,
$$p$$ e $$q$$ inteiros positivos fixados. Prove que $$p|a$$ ou $$q|b$$.
Obs.: As peças não podem ser rotacionadas. Em outras palavras, uma peça $$1$$ × $$k$$ é diferente de uma peça $$k$$ × $$1$$.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]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$$[/spoiler]
Problema 10. Encontre o número de subconjuntos não-vazios de $$\{1,2,\dots,p\}$$ tais que a soma de seus elementos é múltipla de $$p$$, onde $$p$$ é um primo ímpar.
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]
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$$.
[/spoiler]
Problema 11. (IMO 1995) Seja $$p$$ um primo ímpar. Quantos subconjuntos do conjunto $$\{1,2,…,2p\}$$ de $$p$$ elementos e cuja soma dos elementos é múltipla de $$p$$ existem (em função de $$p$$).
[spoiler title=’Solução’ style=’default’ collapse_link=’true’]
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$$
[/spoiler]