دنباله $
1\mathrm{,}1\mathrm{,}2\mathrm{,}4\mathrm{,}7\mathrm{,}\mathrm{13}\mathrm{,...}
$
یک دنباله بازگشتیه که از جمله چهار به بعد هر جمله برابر با مجموع سه جمله قبلی خودشه .
کسی میدونه جمله عمومی این دنباله بازگشتی رو ؟
جمله عمومی یک دنباله بازگشتی
Re: جمله عمومی یک دنباله بازگشتی
سلام در کتاب مبانی ترکیبیات گریمالدی روشی ارائه شده که هر رابطه ی بازگشتی خطی رو میشه حل کرد
-
rohamavation
نام: roham hesami radرهام حسامی راد
محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2
عضویت : سه‌شنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴
پست: 3289-
سپاس: 5494
- جنسیت:
تماس:
Re: جمله عمومی یک دنباله بازگشتی
به‌طور کلی دنباله‌های بازگشتی از قاعده و قانون خاصی پیروی نمیکنند.یک روش خوب استفاده از یک تابع تولیدproduction function هستش میدونی یک دنباله بازگشتیRecurrence relation ثابت یک دنباله بی نهایت از اعداده ببین منظورت اعداد تریبوناچی Tribonacci numbersهست کلا یک دنباله بازگشتی${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},}
$وضرایب ریشه هایش${\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}$
به طور کلی دنباله ای از اعداد
${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots } $در صورتی که یک رابطه تکراری را برآورده کنه بازگشتی ثابت است${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}
$جایی که $c_{i} $ثابت هستن. به عنوان مثال، دنباله فیبوناچی رابطه بازگشتی را مهیا میکنه از نظر تولید توابع
$f(x)=\sum\limits_{n=0}^\infty F_nx^n$تعریف دنباله فیبوناچی با استفاده از تابع مولد.
یک دنباله حالت خطی است (مانند اعداد فیبوناچی) با جبر خطی فرض کنید .$x_n = a_1 x_{n-1} + a_2 x_{n-2} +\cdots +a_k x_{n-k} = \sum_{j=1}^k a_j x_{n-j}$
جوابتون میبینیم که عبارت بعدی در واقع 24 است. این به این دلیله که الگو دقیقاً دو جمله قبلی را جمع نمیکنه بلکه دو جمله قبلی را جمع میکند و اولین جمله قبلی را کم میکنه. بنابراین دنباله : 1، 1، 2، 4، 7، 13، 24، 44، 81، 149، ...هست$An=(An-1)+(An-2)+(An-3)$
ببین $T_n=T_(n-1)+T_(n-2)+T_(n-3)$برای n>=4 آنها حالت n=3 اعداد n مرحله ای فیبوناچی را نشون میدن$1, 1, 2, 4, 7, 13, 24, 44, 81, 149$ اعداد تربوناچی کامل هستند. یعنی هر عدد مثبت را میتوان به صورت مجموع اعداد مجزای تربوناچی نوشت. $اعداد تربوناچی 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504$سری تربوناچی تعمیم دنباله فیبوناچیه که در آن هر جمله مجموع سه جمله قبلیه$a(n) = a(n-1) + a(n-2) + a(n-3) with a(0) = a(1) = 0, a(2) = 1.$یعنی$S_n=T_{n-2}\,S_1+(T_{n-2}+T_{n-3})\,S_2+T_{n-1}\,S_3$
میشه بگم از توابع تولید کننده استفاده کنیدرابطه بازگشت $t_{n + 3} = t_{n + 2} + t_{n + 1} + t_n$ با $t_0 = 0$ ، t1=1، t2=2 مولد $T(z) = \sum_{n \ge 0} t_n z^n$
.بازگشت را در zn ضرب کنید$\frac{T(z) - t_0 - t_1 z - t_2 z^2}{z^3}
= \frac{T(z) - t_0 - t_1 z}{z^2}
+ \frac{T(z) - t_0}{z}
+ T(z)$که$T(z) = \frac{z }{1 - z - z^2 - z^3}$ریشه هایش محاسبه که $t_n \sim c \cdot 1.83^n$
من در مورد یافتن یک فرمول صریح برای اعداد تربوناچی فکر کرده ام که در آن$a_n = a_{n-1}+a_{n-2}+a_{n-3}$و$a_1 = 0, a_1 = 1, a_2 = 1.$
اما در مورد توالی کلی$a_n = xa_{n-1}+ya_{n-2}+za_{n-3}$ با $a_1, a_2,$ و a3.دلخواه فرمول صریح تربوناچی چگونه محاسبه میشود؟
:فکر کنم $a_n = Ar_1^n - Br_2^n,$و$r_1=r_2$ خوب AوB هم${\displaystyle \A ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618\ldots }$و ${\displaystyle B ={\frac {1-{\sqrt {5}}}{2}}\approx -0.618\ldots }$حالr هم${\frac {1}{\sqrt {5}}}$ در نهایت $\sqrt{5} F_n=(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n$
تابع مولد$ z/(1-z-z^2-z^3)$
آیا روشی برای یافتن عبارت کلی یک دنباله بازگشتی وجود داره
با توجه به $(a_{n})_{n \in \mathbb{N}}$ و،$a_{0} = 2, a_{1} = 4, a_{n+2} = 4a_{n+1} - 3a_{n}$
آیا راهی برای یافتن جمله کلی وجود داره؟ من حساب کردم که هر $a_{i}$
ضریب 2 است و سپس سری به 1، 2، 5، 14، 41، ... میشه و معلومه که$a_{i} = 3(a_{i-1}) - 1$
آره! یک رابطه بازگشت خطی مرتبه دوم را در نظر بگیرین
$a_n = b a_{n-1} + c a_{n-2}.$روش استاندارد در نظر گرفتن معادله $r^2 = br + c.$ریشه های این معادله را پیدا میکنم $r_1, r_2$، سپس رابطه بازگشتی ام راه حل کلی را داره$a_n = Ar_1^n + Br_2^n,$
جایی که A,B ثابت هایی هستند که با مقادیر اولیهام تعیین میشن. وقتی یک ریشه مکرر r بدست میارم
$a_n = (An + B)r^n.$بنابراین معادله مشخصه ام تبدیل میشود$r^2 = 4r - 3 \iff r^2 - 4r + 3 = 0 \iff (r - 3)(r - 1) = 0 \iff r = 1 \text{ or } 3,$بنابراین راه حل کلی ام اینه
$a_n = A1^n + B3^n = A + 3^n B.$پس $a_n = 1 + 3^n$
.روش دوم
نوشتن هر جفت عبارت متوالی به صورت ترکیب خطی از جفت جمله های متوالی قبلی$\pmatrix{a_{n}\\a_{n-1}} = \pmatrix{4&-3\\1&0}\pmatrix{a_{n-1}\\a_{n-2}}= \cdots = \pmatrix{4&-3\\1&0}^{n-1}\pmatrix{a_{1}\\a_{0}}$
سوال اینه که چگونه میتوان توان ماتریس را به شکل نزدیک که توسط قطریه نشون داد.$\begin{align*}
\pmatrix{4-\lambda&-3\\1&0-\lambda} &= 0\\
(4-\lambda)(-\lambda) +3 &= 0\\
(\lambda-3)(\lambda-1) &= 0
\end{align*}$
(این معادله مشخصه دارای همان ریشه هایی است که در جواب اولم دادم برای λ=3 دارم$\pmatrix{4&-3\\1&0}\pmatrix{3\\1} = 3\pmatrix{3\\1}$
برای λ=1هم $\pmatrix{4&-3\\1&0}\pmatrix{1\\1} = \pmatrix{1\\1}$بنابراین$\begin{align*}
\pmatrix{4&-3\\1&0}^{n-1} &= \pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{3&1\\1&1}^{-1}\\
&= \frac12\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1&-1\\-1&3}\\
a_n &= \pmatrix{1&0}\pmatrix{a_{n}\\a_{n-1}}\\
&= \pmatrix{1&0}\pmatrix{4&-3\\1&0}^{n-1}\pmatrix{a_{1}\\a_{0}}\\
&= \pmatrix{1&0}\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{3&1\\1&1}^{-1}\pmatrix{4\\2}\\
&= \pmatrix{1&0}\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1&-1\\-1&3}\pmatrix{2\\1}\\
&= \pmatrix{3&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1\\1}\\
&= 3^n+1
\end{align*}$
$وضرایب ریشه هایش${\displaystyle \lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.}$
به طور کلی دنباله ای از اعداد
${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots } $در صورتی که یک رابطه تکراری را برآورده کنه بازگشتی ثابت است${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}
$جایی که $c_{i} $ثابت هستن. به عنوان مثال، دنباله فیبوناچی رابطه بازگشتی را مهیا میکنه از نظر تولید توابع
$f(x)=\sum\limits_{n=0}^\infty F_nx^n$تعریف دنباله فیبوناچی با استفاده از تابع مولد.
یک دنباله حالت خطی است (مانند اعداد فیبوناچی) با جبر خطی فرض کنید .$x_n = a_1 x_{n-1} + a_2 x_{n-2} +\cdots +a_k x_{n-k} = \sum_{j=1}^k a_j x_{n-j}$
جوابتون میبینیم که عبارت بعدی در واقع 24 است. این به این دلیله که الگو دقیقاً دو جمله قبلی را جمع نمیکنه بلکه دو جمله قبلی را جمع میکند و اولین جمله قبلی را کم میکنه. بنابراین دنباله : 1، 1، 2، 4، 7، 13، 24، 44، 81، 149، ...هست$An=(An-1)+(An-2)+(An-3)$
ببین $T_n=T_(n-1)+T_(n-2)+T_(n-3)$برای n>=4 آنها حالت n=3 اعداد n مرحله ای فیبوناچی را نشون میدن$1, 1, 2, 4, 7, 13, 24, 44, 81, 149$ اعداد تربوناچی کامل هستند. یعنی هر عدد مثبت را میتوان به صورت مجموع اعداد مجزای تربوناچی نوشت. $اعداد تربوناچی 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504$سری تربوناچی تعمیم دنباله فیبوناچیه که در آن هر جمله مجموع سه جمله قبلیه$a(n) = a(n-1) + a(n-2) + a(n-3) with a(0) = a(1) = 0, a(2) = 1.$یعنی$S_n=T_{n-2}\,S_1+(T_{n-2}+T_{n-3})\,S_2+T_{n-1}\,S_3$
میشه بگم از توابع تولید کننده استفاده کنیدرابطه بازگشت $t_{n + 3} = t_{n + 2} + t_{n + 1} + t_n$ با $t_0 = 0$ ، t1=1، t2=2 مولد $T(z) = \sum_{n \ge 0} t_n z^n$
.بازگشت را در zn ضرب کنید$\frac{T(z) - t_0 - t_1 z - t_2 z^2}{z^3}
= \frac{T(z) - t_0 - t_1 z}{z^2}
+ \frac{T(z) - t_0}{z}
+ T(z)$که$T(z) = \frac{z }{1 - z - z^2 - z^3}$ریشه هایش محاسبه که $t_n \sim c \cdot 1.83^n$
من در مورد یافتن یک فرمول صریح برای اعداد تربوناچی فکر کرده ام که در آن$a_n = a_{n-1}+a_{n-2}+a_{n-3}$و$a_1 = 0, a_1 = 1, a_2 = 1.$
اما در مورد توالی کلی$a_n = xa_{n-1}+ya_{n-2}+za_{n-3}$ با $a_1, a_2,$ و a3.دلخواه فرمول صریح تربوناچی چگونه محاسبه میشود؟
:فکر کنم $a_n = Ar_1^n - Br_2^n,$و$r_1=r_2$ خوب AوB هم${\displaystyle \A ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618\ldots }$و ${\displaystyle B ={\frac {1-{\sqrt {5}}}{2}}\approx -0.618\ldots }$حالr هم${\frac {1}{\sqrt {5}}}$ در نهایت $\sqrt{5} F_n=(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n$
تابع مولد$ z/(1-z-z^2-z^3)$
آیا روشی برای یافتن عبارت کلی یک دنباله بازگشتی وجود داره
با توجه به $(a_{n})_{n \in \mathbb{N}}$ و،$a_{0} = 2, a_{1} = 4, a_{n+2} = 4a_{n+1} - 3a_{n}$
آیا راهی برای یافتن جمله کلی وجود داره؟ من حساب کردم که هر $a_{i}$
ضریب 2 است و سپس سری به 1، 2، 5، 14، 41، ... میشه و معلومه که$a_{i} = 3(a_{i-1}) - 1$
آره! یک رابطه بازگشت خطی مرتبه دوم را در نظر بگیرین
$a_n = b a_{n-1} + c a_{n-2}.$روش استاندارد در نظر گرفتن معادله $r^2 = br + c.$ریشه های این معادله را پیدا میکنم $r_1, r_2$، سپس رابطه بازگشتی ام راه حل کلی را داره$a_n = Ar_1^n + Br_2^n,$
جایی که A,B ثابت هایی هستند که با مقادیر اولیهام تعیین میشن. وقتی یک ریشه مکرر r بدست میارم
$a_n = (An + B)r^n.$بنابراین معادله مشخصه ام تبدیل میشود$r^2 = 4r - 3 \iff r^2 - 4r + 3 = 0 \iff (r - 3)(r - 1) = 0 \iff r = 1 \text{ or } 3,$بنابراین راه حل کلی ام اینه
$a_n = A1^n + B3^n = A + 3^n B.$پس $a_n = 1 + 3^n$
.روش دوم
نوشتن هر جفت عبارت متوالی به صورت ترکیب خطی از جفت جمله های متوالی قبلی$\pmatrix{a_{n}\\a_{n-1}} = \pmatrix{4&-3\\1&0}\pmatrix{a_{n-1}\\a_{n-2}}= \cdots = \pmatrix{4&-3\\1&0}^{n-1}\pmatrix{a_{1}\\a_{0}}$
سوال اینه که چگونه میتوان توان ماتریس را به شکل نزدیک که توسط قطریه نشون داد.$\begin{align*}
\pmatrix{4-\lambda&-3\\1&0-\lambda} &= 0\\
(4-\lambda)(-\lambda) +3 &= 0\\
(\lambda-3)(\lambda-1) &= 0
\end{align*}$
(این معادله مشخصه دارای همان ریشه هایی است که در جواب اولم دادم برای λ=3 دارم$\pmatrix{4&-3\\1&0}\pmatrix{3\\1} = 3\pmatrix{3\\1}$
برای λ=1هم $\pmatrix{4&-3\\1&0}\pmatrix{1\\1} = \pmatrix{1\\1}$بنابراین$\begin{align*}
\pmatrix{4&-3\\1&0}^{n-1} &= \pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{3&1\\1&1}^{-1}\\
&= \frac12\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1&-1\\-1&3}\\
a_n &= \pmatrix{1&0}\pmatrix{a_{n}\\a_{n-1}}\\
&= \pmatrix{1&0}\pmatrix{4&-3\\1&0}^{n-1}\pmatrix{a_{1}\\a_{0}}\\
&= \pmatrix{1&0}\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{3&1\\1&1}^{-1}\pmatrix{4\\2}\\
&= \pmatrix{1&0}\pmatrix{3&1\\1&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1&-1\\-1&3}\pmatrix{2\\1}\\
&= \pmatrix{3&1}\pmatrix{3^{n-1}&0\\0&1}\pmatrix{1\\1}\\
&= 3^n+1
\end{align*}$
