Soal dari Monthly

Soal dari Monthly

08:34:00   Univ,

Beberapa minggu yang lalu, saya sempat pengen mengirim jawaban ke rubrik American Mathematical Monthly tapi pas saya cek deadline nya sudah lewat, jadi ya saya post disini saja.

11876 Let $a$ and $b$ be the roots of $x^2+x+\frac{1}{2}=0$. Find\[\sum_{n=1}^{\infty} \frac{(-1)^n (a^n+b^n)}{n+2} \]

Solution

Define the sequence $\{a_n\}_{n\geq 0}$ as
\[a_n := (-1)^n (a^n+b^n)  \]
where $a$ and $b$ are the roots of $x^2+x+\frac{1}{2}=0$.

Note that $\alpha:=-a$ and $\beta:=-b$ are  the roots of quadratic equation $x^2-x+\frac{1}{2}=0$, and so $a_n$ can also be written as \[a_n= (-a)^n + (-b)^n = \alpha^n+\beta^n.\] We can directly check that $a_0=2$, and by Viete's Formula we have $a_1=\alpha+\beta=1$ and $a_2=\alpha^2 + \beta^2= (\alpha+\beta)^2-2\alpha \beta= 1-1=0$.


Also by multiplying the equation with $\alpha^n$ we have $\alpha^{n+2} = \alpha^{n+1}-\frac{\alpha^n}{2}$, similarly $\beta^{n+2} = \beta^{n+1}-\frac{\beta^n}{2}$ and hence

\begin{align*} \alpha^{n+2} + \beta^{n+2} = \alpha^{n+1} + \beta^{n+1} - \frac{\alpha^n + \beta^n}{2} \end{align*}
Therefore we have the following recursive formula for the sequence $a_n = (-1)^n (a^n + b^n) = \alpha^n + \beta^n$
\[ a_0=  2\quad a_1=1 \qquad a_{n+2} =  a_{n+1} - \frac{a_n}{2} \quad n\geq 0 \]

Since $a_2 = \alpha^2+\beta^2 = 0$, we have for $j \geq 0$ \[a_{4j+2} = (\alpha^2)^{2j+1} + (\beta^2)^{2j+1} = (\alpha^2+\beta^2)(\alpha^{2j-1} + \cdots + \alpha^{2j-1})=0\]
Thus by the recursive formula
\[a_{4j+3} = -\frac{a_{4j+1}}{2} \qquad \text{and}\qquad a_{4j+4} = a_{4j+3} \qquad  \text{for $j\geq 0$} \]
This gives us the formula of $a_{4k+1}$  which is
\[ a_{4k+1} = a_{4k} - \frac{a_{4k-1}}{2} = \frac{a_{4k-1}}{2} = -\frac{a_{4(k-1)+1}}{4}  = \frac{a_{4(k-2)+1}}{4^2}=\cdots  = \frac{(-1)^{k}}{4^{k}} a_1 =  \frac{(-1)^{k}}{4^{k}}\]
From $a_{4k+2}=0$ and $a_{4k+2} = a_{4k+1} - \frac{a_{4k}}{2}$ we have \[ a_{4k} =2 a_{4k+1} =2\cdot \frac{(-1)^k}{4^k}\]
And using $a_{4k+3} = -\frac{a_{4k+1}}{2}$ we have
\[a_{4k+3}  = \frac{(-1)^{k+1} }{2\cdot 4^k} =  2\cdot \frac{(-1)^{k+1}}{ 4^{k+1}} \]
So the formula for $a_n$ is

\[a_{4k} = 2\cdot \frac{(-1)^k}{4^k} \qquad  a_{4k+1}=\frac{(-1)^{k}}{4^{k}} \qquad a_{4k+2}=0 \qquad a_{4k+3}=2\cdot \frac{(-1)^{k+1}}{ 4^{k+1}} \]
For $|x| \leq 1$, we have for any $n \geq 1$
\[ \left| a_n x^{n+1} \right| \leq |a_{n}| \]
While
\[\sum_{n=1}^{\infty} |a_n| = \sum_{j=1}^{\infty} \left(\frac{2}{4^j} + \frac{1}{4^j} + \frac{2}{4^{j+1}} \right) = \frac{7}{6}\]


Therefore  by the Weierstrass M-Test, $\sum_{n=1}^{\infty} a_n x^{n+1}$ converges uniformly on $[-1,1]$, let say it converges to a function $f(x)$. We have

\begin{align*} f(x)=\sum_{n=1}^{\infty}a_n x^{n+1} &= \sum_{n=1}^{\infty} a_{n+2} x^{n+3}  + a_2 x^3  + a_1 x^2 \\ &=  \sum_{n=1}^{\infty} a_{n+1}x^{n+3} - \sum_{n=1}^{\infty} \frac{a_{n}}{2}x^{n+3} + a_2 x^3  + a_1 x^2  \\ &= xf(x) -\frac{x^2f(x)}{2} + x^2  \end{align*}

Thus
\[f(x)=\frac{2x^2}{x^2-2x+2} \]

By uniform convergence we have

\[\int_0^1 f(x) \, dx = \int_0^1 \sum_{n=1}^{\infty}a_n x^{n+1} \, dx = \sum_{n=1}^{\infty} \int_0^1 a_n x^{n+1} \, dx = \sum_{n=1}^{\infty} \frac{a_n}{n+2}  \]

Therefore the sum equals to

\[\int_0^1 \frac{2x^2}{(x^2-2x+2)}\, dx = \int_0^1 1 + \frac{4x-4}{x^2-2x+2} \, dx =  2x + 2\ln (x^2-2x+2) \bigg|_0^1 = 2-2\ln 2 \]

Continue Reading

Soal Partisi Bilangan Bulat.

Soal Partisi Bilangan Bulat.

00:17:00   Olimpiade Matematika, Umum,

Beberapa hari yang lalu, saya diberi soal berikut oleh Erlang Wiratama Surya :

Diberikan himpunan $X \subset \mathbb{Z}$ dan misalkan $a_1, a_2, \cdots, a_n$ adalah bilangan bulat sedemikian sehingga
\[\mathbb{Z} = \bigcup_{j=1}^n (X+a_j)\]
dan $X+a_i \cap X+a_j = \emptyset$ untuk sebarang $i\neq j$.  Buktikan bahwa terdapat bilangan  bulat tak-nol $p$ sedemikian sehingga $X+p=X$.(Disini definisi dari $X+d:= \{x+d | x \in X\}$ ).

Katanya soal ini ada di Sesi Mandiri Pembinaan IMO Tahap 4.

Sebenarnya saya sudah pernah lihat soal ini sebelumnya (dan waktu itu saya tidak bisa menyelesaikannya).  Tapi sudah lupa dimana.

Sampai sekarang, saya masih penasaran tentang dimana saya melihat soal ini (saya memang sering berasa tidak lega dan agak annoying kalo ada sesuatu berasa di ujung lidah seperti ini :/  )

Bahkan setelah beberapa hari, saya berhasil menyelesaikan soal ini, tapi masih belum tahu source nya (sampai bikin thread di math.stackexcange menanyakan sumber).

Saya  (secara dejavu) merasa  ini bukan soal yang bersumber dari olimpiade, tapi dari matematika popular yang saya pernah baca di blog-blog post beken (Terence Tao, Timothy Gowers, dll)

Anyway ini solusinya, lagi-lagi saya pakai sesuatu yang sering saya pakai beberapa bulan terakhir (lihat soal kompetisi olimpiade.org no 4 buatan saya dan juga teknik yang sama di mini-artikel yang saya tulis ini ) yaitu kombinasi dari Indicator Function + PigeonHole Principle.

Solusi: 
Pertama-tama perhatikan bahwa apabila kita pilih bilangan asli $d$ sedemikian sehingga $a_i^{\prime}=a_i + d$ semua positif maka himpunan $X=X^{\prime} - d$ juga memenuhi

\[\mathbb{Z} = \bigcup_{i=1}^n (X^{\prime} + a_i^{\prime})\]

dan $X^{\prime} + a_i^{\prime} \cap X^{\prime} + a_j^{\prime} = \emptyset$. Lalu, apabila kita berhasil membuktikan $X^{\prime} + p^{\prime} = X^{\prime}$ maka diperoleh $X+p-d= X-d$, jadi $X+p=X$, dan soal terbukti.  Ini berarti pengubahan $a_i \rightarrow a_i^{\prime}$ tidak mengubah maksud soal.

Sehingga tanpa kehilangan keumuman soal bisa diasumsikan semua $a_i$ positif, dan tanpa kehilangan keumuman juga bisa diasumsikan $a_n > a_{n-1} > \cdots  > a_1$.

Sekarang kita definisikan fungsi indikator

\[v_i = \begin{cases} 1 & \text{jika $i\in X$, } \\ 0 & \text{jika tidak} \end{cases} \]

Idenya adalah dengan membuktikan bahwa fungsi indikator $v_i$ periodik, yakni $v_{i+p} =v_i$ untuk suatu $p$.

Maka dari kondisi $X+a_1, X+a_2, \cdots, X+a_n$ adalah partisi dari $\mathbb{Z}$,  diperoleh untuk setiap bilangan bulat $r$ berlaku

\[v_{r-a_1} + v_{r-a_2} + \cdots + v_{r-a_n} = 1\]

Sekarang misalkan $\lambda=a_n - a_1$.  Persamaan diatas adalah relasi rekursif, jadi apabila kita mempunyai informasi nilai awal  paling banyak $\lambda=a_n-a_1$ buah, maka solusi rekursif tersebut akan unik.

Jadi apabila nilai dari

\[v_{r+1}, v_{r+2}, \cdots, v_{r+\lambda}\]

diketahui maka nilai $v_i$ akan bisa di-generate  untuk setiap $i$. Karena $v_i$ hanya bisa nol atau satu, maka kemungkinan nilai awal diatas  hanya ada $2^{\lambda}$. Jadi apabila kita bentuk block-block dengan panjang $\lambda$ :

\[\cdots ,  \{ v_{-\lambda-1},  \cdots, v_{-1}, v_0\} , \{v_1, v_2, \cdots, v_{\lambda} \} , \{v_{\lambda+1}, v_{\lambda+1}, \cdots, v_{2 \lambda}\} , \cdots , \{v_{r+1}, v_{r+2}, \cdots , v_{r+\lambda}\}, \cdots  \]

 maka berdasarkan prinsip PigeonHole terdapat $u_1$ dan $u_2$ sedemikian sehingga

\[v_{u_1+i}=v_{u_2+i} \qquad i=1, \cdots, \lambda \]

dan karena block $v_{u_1 + 1}, v_{u_1+2}, \cdots , v_{u_1 + \lambda}$ men-generate nilai $v_i$,   maka  $v_{u_2 + 1}, v_{u_1+2}, \cdots , v_{u_2 + \lambda}$ juga men-generate nilai $v_i$ yang sama, jadi  nilai setelah $u_2$ mengulangi nilai setelah $u_1$, dan nilai sebelum $u_2+1$ mengulangi nilai sebelum $u_1+1$, sehingga $v_i$ periodic.

Ini berarti terdapat $p \neq 0$ sedemikian sehingga $v_{i+p} = v_i$,  untuk setiap $i$. Sehingga jika $h \in X$ jika dan hanya jika $v_{h} = 1 = v_{h+p}$ jika dan hanya jika $h+p \in X$. Terbukti.

Continue Reading