به نام خدا
رابطهٔ بازگشتی زیر را در نظر بگیرید:
$$a_n=2a_{n-1},a_0=3$$
برای حل روابط بازگشتیای بهاین شکل، میتوانیم از یک استقرای ریاضی ساده استفاده کنیم. بهاین صورت است:
ابتدا بجای $n$، $n-1$ را قرار میدهیم:
$$a_n=2a_{n-1} \Rightarrow a_{n-1}=2a_{n-2}$$
بنابراین:
$$a_n=2^2a_{n-2}$$
ولی اگر بجای $n$، $n-2$ را قرار میدادیم، نتیجه بهاین شکل میشد:
$$a_n=2^3a_{n-3}$$
بهاین ترتیب اگر بجای $n$، $n-3$ را قرار میدادیم، نتیجه بهاین شکل میشد:
$$a_n=2^4a_{n-4}$$
و اگر بجای $n$، $n-4$ را قرار میدادیم، نتیجه بهاین شکل میشد:
$$a_n=2^5a_{n-5}$$
خوب، حالا با کمی دقت، خیلی زیبا و راحت میتوان نتیجهگرفت که:
$$a_n=2^na_{n-n} \Rightarrow a_n=a_0 \cdot 2^n$$
و با شرط اینکه $a_0=3$، داریم:
$$a_n=3 \cdot 2^n$$
بنابراین توانستیم این رابطهٔ بازگشتی را حل کنیم.
مثالی دیگر:
رابطهٔ بازگشتی زیر را حل کنید:
$$a_n=a_{n-1}+4,a_0=2$$
مثل رابطهٔ بازگشتی قبل، ابتدا بجای $n$، $n-1$ را قرار میدهیم:
$$a_n=a_{n-1}+4 \Rightarrow a_{n-1}=a_{n-2}+4$$
بنابراین:
$$a_n=4 \cdot 2+a_{n-2}$$
ولی اگر بجای $n$، $n-2$ را قرار میدادیم، نتیجه بهاین شکل میشد:
$$a_n=4 \cdot 3+a_{n-3}$$
بهاین ترتیب اگر بجای $n$، $n-3$ را قرار میدادیم، نتیجه بهاین شکل میشد:
$$a_n=4 \cdot 4+a_{n-4}$$
و اگر بجای $n$، $n-4$ را قرار میدادیم، نتیجه بهاین شکل میشد:
$$a_n=4 \cdot 5+a_{n-5}$$
خوب، حالا با کمی دقت، خیلی زیبا و راحت میتوان نتیجهگرفت که:
$$a_n=4n+a_{n-n} \Rightarrow a_n=4n+a_0$$
و با شرط اینکه $a_0=2$، داریم:
$$a_n=4n+2$$
