Penjumlahan Berbagai Urutan
Pengantar Pemecahan Masalah
Pemecahan masalah atau problem solving adalah proses untuk menemukan solusi dari suatu masalah dengan menggunakan pengetahuan dan keterampilan yang sudah ada. Pemecahan masalah merupakan soft skill yang penting untuk menghadapi tantangan dalam kehidupan sehari – hari, terutama ketika harus menemukan solusi inovatif untuk masalah yang rumit
- Definisi
- Contoh Soal
Definisi
Penjumlahan Deret merupakan alat umum yang digunakan di setiap cabang kompetisi olimpiade matematika, sehingga terdapat berbagai metode untuk mengevaluasi penjumlahan deret.
Selain penjumlahan sebagian dari suatu A.P., suatu G.P., dan deret rekursif yang telah kita bahas sebelumnya, dalam kuliah ini kita akan memperkenalkan deret lain yang muncul dalam Aljabar, Trigonometri, Polinomial, Teori Bilangan, dan Kombinatorika.
Namun, bab ini tidak komprehensif. Kita tidak akan membahas pertidaksamaan penjumlahan dan bilangan kompleks serta identitas kombinatorial yang rumit agar pembaca di tingkat senior dapat lebih mudah memahaminya.
Contoh Soal
- Barisan $\{a_n\}$ dan $\{b_n\}$ memenuhi $a_kb_k=1,k=1,2,…$ Jika jumlah suku pertama $n$ pada $\{a_n\}$ adalah $A_n=\frac{n(n+1)(n+2)}{3}$, tentukan jumlah $B_n$ dari $n$ suku pertama $\{b_n\}$.
Solusi: $a_1=A_1=\frac{1\cdot 2\cdot 3}{3}=2$, dan untuk $n\ge 2$ $$a_n =A_n-A_{n-1}=\frac{n(n+1)(n+2)}{3}-\frac{(n-1)n(n+1)}{3}$$ $$=\frac{n(n+1)[(n+2)-(n-1)]}{3}=n(n+1).$$ Oleh karena itu $b_n=\frac{1}{a_n}=\frac{1}{n(n+1)}$ untuk $n\ge 1$. Maka $$B_n=\sum_{k=1}^{n}\frac{1}{k(k+1)}=\sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right)=1-\frac{1}{n+1}=\frac{n}{n+1}$$ untuk $n=1,2,…$. - Misalkan $n$ bilangan asli apapun. Buktikan identitas $$\sum_{k=1}^{n}\frac{k}{k^4+k^2+1}=\frac{1}{n^2+n+1}\sum_{k=1}^{n}k.$$ Solusi: Untuk setiap bilangan asli $n$, $$\sum_{k=1}^{n}\frac{k}{k^4+k^2+1}=\sum_{k=1}^{n}\frac{k}{(k^4+2k^2+1)-k^2}=\sum_{k=1}^{n}\frac{k}{(k^2+1)^2-k^2}$$ $$=\sum_{k=1}^{k}\frac{k}{(k^2+1-k)(k^2+1+k)}=\frac{1}{2}\sum_{k=1}^{n}\left(\frac{1}{k^2+1-k}-\frac{1}{k^2+1+k}\right)$$ $$\frac{1}{2}\left(1-\frac{1}{n^2+1+n}\right)=\frac{1}{2}\cdot \frac{n^2+n}{n^2+1+n}$$ $$=\frac{1}{n^2+n+1}\cdot \frac{n(n+1)}{2}=\frac{1}{n^2+n+1}\sum_{k=1}^{n}k.$$
- Evaluasi $$\frac{\sum_{n=1}^{99}\sqrt{10+\sqrt{n}}}{\sum_{n=1}^{99}\sqrt{10-\sqrt{n}}}$$
Solusi: Misalkan $S=\sum_{n=1}^{99}\sqrt{10+\sqrt{n}},T=\sum_{n=1}^{99}\sqrt{10-\sqrt{n}}$. Perhatikan bahwa $\sqrt{a+b+2\sqrt{ab}}=\sqrt{a}+\sqrt{b}$ untuk bilangan riil positif $a$ dan $b$. Secara khusus, untuk setiap bilangan bulat positif tetap $n$ dengan $1\le n\le 99$, pilih $a>b>0$ memenuhi $a+b=20,ab=n$, maka $a,b$ adalah akar dari persamaan $x^2-20x+n=0$, yaitu $$a=10+\sqrt{100-n},\text{ }\text{ }\text{ }b=10-\sqrt{100-n}.$$ Maka $$\sqrt{2}S=\sum_{n=1}^{99}\sqrt{20+2\sqrt{n}}=\sum_{n=1}^{99}\left(\sqrt{10+\sqrt{10+\sqrt{100-n}}}+\sqrt{10-\sqrt{100-n}}\right)$$ $$=\sum_{n=1}^{99}\left(\sqrt{10+\sqrt{n}}+\sqrt{10-\sqrt{n}}\right)=S+T.$$ Jadi, $$(\sqrt{2}-1)S=T\Rightarrow \frac{S}{T}=\frac{1}{\sqrt{2}-1}=1+\sqrt{2}.$$ - Dalam barisan $\{x_n\},x_1=1$ dan $x_{n+1}=\frac{\sqrt{3}x_n+1}{\sqrt{3}-x_n}$ untuk $n\in\mathbb{N}$. Tentukan $sum_{k=1}^{2008}x_k$.
Solusi: Perhatikan bahwa jika kita misalkan $x_n=\tan \theta_n,n\in,\mathbb{N}$, dimana $\theta_1=\frac{\pi}{4}$, maka $$x_{n+1}=\frac{\sqrt{3}x_n+1}{\sqrt{3}-x_n}=\frac{x_n+\frac{1}{\sqrt{3}}}{1-\frac{1}{\sqrt{3}}x_n}=\tan\left(\theta_n+\frac{\pi}{6}\right).$$ Oleh karena itu $\theta_{n+1}\equiv \theta_n+\frac{\pi}{6}$ (mod $\pi$) untuk $n\in\mathbb{N}$, dan juga $\{x_n\}$ bersifat periodik dengan periode panjang $6$.
Mudah untuk mencari $$x_1=1,x_2=2+\sqrt{3},x_3=-2-\sqrt{3},x_4=-1,x_5=-2+\sqrt{3},x_6=2-\sqrt{3}.$$ Maka $x_1+x_2+…+x_5+x_6=0$ dan $2008=6\times 334 +4$ menyiratkan bahwa $$\sum_{k=1}^{2008}x_k=x_1+x_2+x_3+x_4=0.$$ - Tentukan ekspresi sederhana dari $$S_n=\left\lfloor \sqrt{1} \right\rfloor+\left\lfloor\sqrt{2} \right\rfloor+…+\left\lfloor \sqrt{n^2-1} \right\rfloor,$$ dalam suku $n$.
Solusi: Pertidaksamaan $(n-1)^2<n^2-1<n^2$ menyiratkan bahwa $\left\lfloor \sqrt{n^2-1} \right\rfloor=n-1$, maka suku terakhir $S_n$ adalah $n-1$.
Di bawah ini kita menghitung jumlah suku dalam $S_n$ yang sama dengan $k$ untuk $1\le k\le n-1$. Karena suku-suku nya adalah $$\left\lfloor \sqrt{k^2} \right\rfloor,\left\lfloor \sqrt{k^2+1} \right\rfloor,…,\left\lfloor \sqrt{(k+1)^2-1} \right\rfloor,$$ maka bilangan nya adalah $[(k+1)^2-1]-[k^2-1]=(k+1)^2-k^2$. Maka, $$S_n=\sum_{k=1}^{n-1}k[(k+1)^2-k^2]=\sum_{ }^{n-1}(2k^2+k)$$ $$=\frac{(n-1)n(2n-1)}{3}+\frac{n(n-1)}{2}=\frac{n(n-1)(4n+1)}{6}.$$ - Temukan sisa $S =\sum_{i=1}^{2009}i\cdot\binom{2008}{i-1}$ ketika dibagi dengan 2008.
Solusi: Perhatikan bahwa $$2S\sum_{i=1}^{2009}\binom{2008}{i-1}+\sum_{i=1}^{2009}(2010-i)\binom{2008}{i-1}=2010\sum_{i=1}^{2009}\binom{2008}{i-1}$$ $$=2010\sum_{i=1}^{2008}\binom{2008}{i}=2010\times 2^{2008}\Rightarrow S=2010\cdot 2^{2007}.$$ Maka, $S\equiv 2\cdot 2^{2007}\equiv 2^{2008}$ (mod $2008$). Dengan Teorema Kecil Fermat, $2^{250}\equiv 1$ (mod $251$), jadi $$2^{2008}=(2^{250})^8\cdot 2^8=251m +2^8\Rightarrow m=8k\Rightarrow 2^{2008}=2008k+256,$$ yaitu, sisa nya adalah $256$. - Misalkan $a_1,a_2,a_3,a_4,a_5$ menjadi bilangan riil yang memenuhi persamaan: $$\frac{a_1}{k^2+1}+\frac{a_2}{k^2+2}+\frac{a_3}{k^2+3}+\frac{a_4}{k^2+4}+\frac{a_5}{k^2+5}=\frac{1}{k^2}\text{ untuk }k=1,2,3,4,5.$$ Tentukan nilai dari $\frac{a_1}{37}+\frac{a_2}{38}+\frac{a_3}{39}+\frac{a_4}{40}+\frac{a_5}{41}$. (Ekspresikan nilai sebagai pecahan tunggal.)
Solusi: Misalkan $R(x):=\frac{a_1}{x^2+1}+\frac{a_2}{x^2+2}+\frac{a_3}{x^2+3}+\frac{a_4}{x^2+4}+\frac{a_5}{x^2+5}.$ Maka $$R(\pm 1)=1,R(\pm 2)=\frac{1}{4},R(\pm 3)=\frac{1}{9},R(\pm 4)=\frac{1}{16},R(\pm 5)=\frac{1}{25}$$ dan $R(6)$ adalah nilai yang akan ditemukan.
Definisikan $P(x):=(x^2+1)(x^2+2)(x^2+3)(x^2+4)(x^2+5)$ dan $Q(x):=R(x)P(x)$. Maka untuk $k=\pm 1,\pm 2, \pm 3,\pm 4,\pm 5$, kita dapatkan $Q(k)=R(k)P(k)=\frac{P(k)}{k^2}$, yaitu $P(k)-k^2Q(k)=0$. Karena $P(x)-x^2Q(x)$ adalah polinomial dari derajat $10$ dengan akar-akar $\pm 1,\pm 2,\pm 3,\pm 4,\pm 5$, kita dapatkan $$P(x)-x^2Q(x)=A(x^2-1)(x^2-4)(x^2-9)(x^2-16)(x^2-25).\text{ }\text{ }\text{ }\text{ }\text{ }(*)$$ Dengan menempatkan $x=0$, kita memperoleh $A=\frac{P(0)}{(-1)(-4)(-9)(-16)(-25)}=-\frac{1}{120}.$
Terakhir, membagi kedua sisi $(*)$ dengan $P(x)$ menghasilkan $$1-x^2R(x)=1-x^2\frac{Q(x)}{P(x)}=-\frac{1}{120}\cdot \frac{(x^2-1)(x^2-4)(x^2-9)(x^2-16)(x^2-25)}{(x^2+1)(x^2+2)(x^2+3)(x^2+4)(x^2+5)}$$ dan maka $$1-36R(6)=-\frac{35\times 32\times 27\times 20\times 11}{120\times 37\times 38\times 39\times 40\times 41}=-\frac{3\times 7\times 11}{13\times 19\times 37\times 41}$$ $$=-\frac{231}{374699},$$ menyiratkan bahwa $R(6)=\frac{1}{6^2}\left[1+\frac{1}{120}\prod_{k=1}^{5}\frac{(6^2-k^2)}{(6^2+k)}\right]=\frac{187465}{6744582}.$
Catatan. Kita dapat memperoleh $a_1=\frac{1105}{72},a_2=-\frac{2673}{40},a_3=\frac{1862}{15},a_4=-\frac{1885}{18},a_5=\frac{1323}{40}$ dengan menyelesaikan sistem persamaan linear yang diberikan, yang sangat berantakan dan memakan banyak waktu. - $f:\mathbb{N}\times \mathbb{Z}\mapsto\mathbb{Z}$ memenuhi kondisi yang diberikan
(a) $f(0,0)=1,f(0,1)=1;$
(b) $\forall k\in \{0,1\},f(0,k)=0;$ dan
(c) $\forall n\ge 1$ dan $k,f(n,k)=f(n-1,k)+f(n-1,k-2n).$
Tentukan jumlah $$\sum_{k=0}^{\binom{2009}{2}}f(2008,k).$$
Solusi: Pertama-tama dengan induksi pada $n$ kita membuktikan bahwa $f(n,k)=0$ untuk $k<0$ atau $n^2+n+1<k$.
Untuk $n=0$, kondisi $(b)$ memberikan $f(0,k)=0$ jika $k<0$ atau $1<k$. Asumsikan bahwa $f(n,k)=0$ jika $k<0$ atau $n^2+n+1<k$, maka untuk $n+1$, dengan kondisi $(c)$, $$f(n+1,k)=f(n,k)+f(n,k-2(n+1))=0\text{ jika }k<0\text{ dan }$$ jika $(n+1)^2+(n+1)+1<k$, maka $n^2+n+1<k-2(n+1),$ maka $$f(n+1,k)=f(n,k)+f(n,k-2(n+1))=0.$$ Pembuktian induktif telah selesai.
Di bawah ini dengan induksi pada $n$ kami menunjukkan bahwa untuk $k\in\mathbb{Z}$ $$f(n,n^2+n+1-k)=f(n,k);\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(19.1)$$ $$\sum_{k=0}^{n^2+n+1}f(n,k)=2^{n+1}.\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(19.2)$$ Untuk $n=0$ kesimpulannya jelas. Asumsikan bahwa $(19.1)$ dan $(19.2)$ benar, lalu verifikasi bahwa pernyataan tersebut masih benar untuk $n+1.$ $$f(n+1,(n+1)^2+(n+1)+1-k)$$ $$=f(n,(n+1)^2+(n+1)+1-k)+f(n,(n+1)^2+(n+1)+1-k-2(n+1))$$ $$=f(n,n^2+n+1-(k-2(n+1)))+f(n,n^2+n+1-k)$$ $$=f(n,k-2(n+1))+f(n,k)=f(n+1,k).$$ Maka $(19.1)$ benar untuk $n+1$. Untuk $(19.2)$, $$\sum_{k=0}^{(n+1)^2+(n+1)+1}f(n+1,k)=\sum_{k=0}^{(n+1)^2+(n+1)+1}[f(n,k-2(n+1))+f(n,k)]$$ $$=\sum_{k=0}^{(n+1)^2+(n+1)+1}f(n,k-2(n+1))+\sum_{k=0}^{(n+1)^2+(n+1)+1}f(n,k)$$ $$=\sum_{k=2(n+1)}^{(n+1)^2+(n+1)+1}f(n,k-2(n+1))+\sum_{k=0}^{n^2+n+1}f(n,k)$$ $$=\sum_{k=0}^{n^2+n+1}f(n,k)+\sum_{k=0}^{n^2+n+1}f(n,k)=2\cdot 2^{n+1}=2^{n+2}.$$ Maka, $(19.2)$ juga benar untuk $n+1$. Karena $$\sum_{k=0}^{\binom{2009}{2}}f(2008,k)=\frac{1}{2}\sum_{k=0}^{2008^2+2008+1}f(2008,k)=\frac{1}{2}\cdot 2^{2009}=2^{2008}.$$ - Evaluasi $$\sum_{k=84}^{8000}\binom{k}{84}\cdot\binom{8084-k}{84}.$$
Solusi: Misalkan $S=\{0,1,2,…,8084\}$. Maka ada total $\binom{8085}{169}$ cara untuk memilih $84+1+84=169$ elemen berbeda dari $S$.
Misalkan $k$ adalah median dari $169$ angka yang dipilih. Maka, rentang nilai $k$ yang mungkin adalah himpunan $T=\{84,85,…,8000\}$.
Untuk setiap nilai $k$ dalam $T$, ada $\binom{k}{84}$ cara memilih $84$ angka yang kurang dari $k$, dan $\binom{8084-k}{84}$ cara memilih $84$ angka yang lebih besar dari $k$, maka $k$ adalah median. Oleh karena itu ada total $\binom{k}{84}\cdot\binom{8084-k}{84}$ cara yang memperoleh median $k$.
Jadi, $$\sum_{k=84}{8000}\binom{k}{84}\cdot\binom{8084-k}{84}=\binom{8085}{169}.$$
“Don’t judge each day by the harvest you reap but by the seeds that you plant.”
