Tag: Rekursif

Misalkan $G(x)$ adalah fungsi pembangkit biasa (FPB) untuk menyelesaikan relasi rekurensi ini, maka haruslah
${\displaystyle \sum _{n=1}^{\mathrm{\infty }}(a_n-a_{n-1})x^n=7}$
Tinjau sukunya satu per satu.
${\displaystyle \sum _{n=1}^{\mathrm{\infty }}{a}_n{x}^n=G(x)-a_0=G(x)-1}$
${\displaystyle \sum _{n=1}^{\mathrm{\infty }}{a}_{n-1}{x}^n=x\sum _{n=1}^{\mathrm{\infty }}{a}_{n-1}{x}^{n-1}=xG(x)}$
Jadi, persamaan di atas dapat ditulis menjadi
$\begin{array}{rl}G(x)-1-xG(x)& =7\\ (1-x)G(x)& =8\\ G(x)& ={\displaystyle \frac{8}{1-x}}={\displaystyle \sum _{n=0}^{\mathrm{\infty }}8x^n}\end{array}$
Jadi, solusi relasi rekurensinya adalah $\boxed{{\displaystyle a_n=8}}$ (barisan konstan yang setiap suku-sukunya $8$).

Relasi rekurensi tersebut merupakan relasi rekurensi homogen dengan koefisien konstan yang dapat diselesaikan dengan mudah. Tetapi, kita akan mencoba menggunakan metode fungsi pembangkit.
Misalkan $G(x)$ fungsi pembangkit biasa (FPB) untuk relasi ini, maka haruslah
$\begin{array}{rl}{\displaystyle \sum _{n=1}^{\mathrm{\infty }}(a_n-2a_{n-1})x^n}& =0\\ \sum _{n=1}^{\mathrm{\infty }}{a}_n{x}^n-2x\sum _{n=1}^{\mathrm{\infty }}{a}_{n-1}{x}^{n-1}& =0\\ (G(x)-a_0)-2xG(x)& =0\\ (1-2x)G(x)& =3\\ G(x)& ={\displaystyle \frac{3}{1-2x}}\\ G(x)& =\sum _{n=0}^{\mathrm{\infty }}3(2^n)x^n\end{array}$
Jadi, solusi relasi rekurensinya adalah $\boxed{{\displaystyle a_n=3(2^n)}}$

Misalkan ${\displaystyle G(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n}$, sehingga bentuk operator sumasi dari barisan rekursif tersebut dapat ditulis menjadi
$$\begin{array}{rl}{\displaystyle \sum _{n=1}^{\mathrm{\infty }}(a_n-3a_{n-1})x^n}& =\sum _{n=1}^{\mathrm{\infty }}{n}^2{x}^n\\ (G(x)-1)-3xG(x)& ={\displaystyle \frac{x^2+x}{(1-x{)}^3}}\\ (1-3x)G(x)& ={\displaystyle \frac{x^2+x}{(1-x{)}^3}}+1\\ G(x)& ={\displaystyle \frac{x^2+x+(1-x{)}^3}{(1-x{)}^3(1-3x)}}\\ G(x)& ={\displaystyle \frac{-x^3+4x^2-2x+1}{(1-x{)}^3(1-3x)}}\end{array}$$Dengan menerapkan teknik dekomposisi pecahan parsial (prosedurnya memang cukup panjang dalam kasus ini), diperoleh
$$\begin{array}{rl}G(x)& ={\displaystyle \frac{-{\displaystyle \frac{13}{8}}}{1-x}}+{\displaystyle \frac{{\displaystyle \frac{9}{4}}}{(1-x{)}^2}}+{\displaystyle \frac{-{\displaystyle \frac{5}{2}}}{(1-x{)}^3}}+{\displaystyle \frac{{\displaystyle \frac{23}{8}}}{1-3x}}\\ & =-{\displaystyle \frac{13}{8}}{\displaystyle \sum _{n=0}^{\mathrm{\infty }}{x}^n+{\displaystyle \frac{9}{4}}\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+1}{n})x^n}\\ & -{\displaystyle \frac{5}{2}}\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+2}{n})x^n+{\displaystyle \frac{23}{8}}\sum _{n=0}^{\mathrm{\infty }}(3x{)}^n\\ & =\sum _{n=0}^{\mathrm{\infty }}(-{\displaystyle \frac{13}{8}}+{\displaystyle \frac{9}{4}}(\genfrac{}{}{0ex}{}{n+1}{1})-{\displaystyle \frac{5}{2}}(\genfrac{}{}{0ex}{}{n+2}{2})+{\displaystyle \frac{23}{8}}\cdot 3^n)x^n\end{array}$$Jadi, didapat
$$\boxed{{\displaystyle a_n=-{\displaystyle \frac{13}{8}}+{\displaystyle \frac{9}{4}}(\genfrac{}{}{0ex}{}{n+1}{1})-{\displaystyle \frac{5}{2}}(\genfrac{}{}{0ex}{}{n+2}{2})+{\displaystyle \frac{23}{8}}\cdot 3^n}}$$

Misalkan ${\displaystyle G(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n}$, sehingga bentuk operator sumasi dari barisan rekursif tersebut dapat ditulis menjadi
$\begin{array}{rl}{\displaystyle \sum _{n=1}^{\mathrm{\infty }}{a}_n{x}^n}& =\sum _{n=1}^{\mathrm{\infty }}(a_{n-1}+n)x^n\\ G(x)-1& =xG(x)+{\displaystyle \frac{x}{(1-x{)}^2}}\\ G(x)(1-x)& ={\displaystyle \frac{x}{(1-x{)}^2}}+{\displaystyle \frac{(1-x{)}^2}{(1-x{)}^2}}\\ G(x)& ={\displaystyle \frac{x+(1-x{)}^2}{(1-x{)}^2(1-x)}}\\ G(x)& ={\displaystyle \frac{1-x+x^2}{(1-x{)}^3}}\end{array}$
Dengan menggunakan teknik dekomposisi pecahan parsial, diperoleh
$$\begin{array}{rl}G(x)& ={\displaystyle \frac{1}{1-x}}-{\displaystyle \frac{1}{(1-x{)}^2}}+{\displaystyle \frac{1}{(1-x{)}^3}}\\ & ={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{x}^n-\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+1}{n})x^n+\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+2}{2})x^n}\\ & =\sum _{n=0}^{\mathrm{\infty }}(1-(n+1)+(\genfrac{}{}{0ex}{}{n+2}{2}))x^n\\ & =\sum _{n=0}^{\mathrm{\infty }}(-n+(\genfrac{}{}{0ex}{}{n+2}{2}))x^n\end{array}$$Jadi, barisan eksplisitnya adalah
$\boxed{{\displaystyle a_n=-n+(\genfrac{}{}{0ex}{}{n+2}{2})}}$

Misalkan $G(x)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n}$ dan perhatikan bahwa
${\displaystyle \sum _{n=0}^{\mathrm{\infty }}{x}^n={\displaystyle \frac{1}{1-x}}}$ ekuivalen dengan ${\displaystyle \sum _{n=1}^{\mathrm{\infty }}{x}^n={\displaystyle \frac{1}{1-x}}-1}$, berarti dapat kita tuliskan bentuk barisan rekursif di atas menjadi
$${\displaystyle \begin{array}{rl}\sum _{n=1}^{\mathrm{\infty }}(a_n-3a_{n-1})x^n& =\sum _{n=1}^{\mathrm{\infty }}(2-2n^2)x^n\\ [G(x)-3]-3xG(x)& ={\displaystyle \frac{2}{1-x}}-2-{\displaystyle \frac{2(x^2+x)}{(1-x{)}^3}}\\ G(x)& ={\displaystyle \frac{-x^3+3x^2-9x+3}{(1-x{)}^3(1-3x)}}\end{array}}$$Uraikan dengan dekomposisi pecahan parsial untuk mendapatkan
$\begin{array}{rl}{\displaystyle G(x)}& ={\displaystyle \frac{2}{(1-x{)}^3}}+{\displaystyle \frac{1}{1-3x}}\\ & =2\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2+n}{n})x^n+\sum _{n=0}^{\mathrm{\infty }}(3x{)}^n\\ & =\sum _{n=0}^{\mathrm{\infty }}(2(\genfrac{}{}{0ex}{}{2+n}{n})+3^n)x^n\end{array}$
Jadi, rumus barisan eksplisitnya adalah
${\displaystyle a_n=2(\genfrac{}{}{0ex}{}{2+n}{n})+3^n=2(\genfrac{}{}{0ex}{}{2+n}{2})+3^n}$
sehingga
$\boxed{{\displaystyle \begin{array}{rl}{a}_{99}& =2(\genfrac{}{}{0ex}{}{2+99}{99})+3^{99}\\ & =3^{99}+{99}^2+299\end{array}}}$