Вышеприведённую явную формулу можно доказать по-разному... а) как указал Shaman, по индукции (конечно, для этого нужно знать эту формулу заранее). б) следуя Мёбиусу с помощью введения генерирующей функции; в) третьим путём - прямым. Приведу на Ваше рассмотрение доказательства, только в обратном порядке... так, по-моему, будет более математически естественно
Исследование ряда Фибоначчи Ещё разок выпишем несколько первых членов ряда Фибоначчи: `1,1,2,3,5,8,13,21,34,...` Как мы можем видеть, ряд Фибоначчи - возрастающая последовательность положительных целых чисел, заданная рекуррентной формулой: 1) `phi_(n+2)=phi_(n+1)+phi_n` и двумя начальными условиями: 0.1) `phi_1=1`, 0.2) `phi_2=1` . Формула 1) задаёт восходящий ход рекурсии. Напишем формулу в нисходящем виде: 2) `phi_n = phi_(n+2)-phi_(n+1)` . Теперь будем последовательно заменять член в формуле справа с меньшим порядковым номером, используя ту же формулу 2. Получим: `phi_n=1*phi_(n+2) - 1*(phi_(n+3) - phi_(n+2)) = (1+1)*phi_(n+2) - 1*phi_(n+3) = (-1)^3*(1*phi_(n+3) - 2*phi_(n+2)) =` `= (-1)^3*(1*phi_(n+3) - 2*(phi_(n+4) - phi_(n+3))) = (-1)^4*(2*phi_(n+4) - 3*phi_(n+3)) = (-1)^(3+1)*(phi_3*phi_(n+4) - phi_4*phi_(n+3))=` `=(-1)^(3+1)*(phi_3*phi_(n+4) - phi_4*(phi_(n+5) - phi_(n+4))) = (-1)^(4+1)*(phi_4*phi_(n+5) - phi_5*phi_(n+4))` Продолжая этот процесс, мы по индукции прийдём к формуле: 3) `phi_n=(-1)^(k+1)*(phi_k*phi_(n+k+1) - phi_(k+1)*phi_(n+k))` , или 3.1) `phi_k*phi_(n+k+1) - phi_(k+1)*phi_(n+k)=(-1)^(k+1)*phi_n` , которая и доказывается по индукции, как мы видим выше явный путь доказательства. Теперь получим дополнительную информацию о последовательности из 3.1, воспользовавшись 1 и первым начальным условием 0.1): `phi_k*phi_(k+2) - phi_(k+1)*phi_(k+1) = (-1)^(k+1)` или, пользуясь 1: `phi_k^2 - phi_k*phi_(k+1) - phi_(k+1)^2 = -(-1)^k`. Окончательно, получим: 4) `phi_(k+1)^2 - phi_(k+1)*phi_k - (phi_k^2 + (-1)^k)=0` . Как видим, 4 есть квадратное уравнение относительно `phi_(k+1)` , как, впрочем, и относительно `phi_k` . Решая его, и учитывая, что `phi_(k+1)>phi_k`, получим: 5) `phi_(k+1) = (phi_k + sqrt(5*phi_k^2 + 4*(-1)^k))/2` . Мы уже явно наблюдаем намёк на величину `alpha = (1+sqrt(5))/2` !
Вставлю-ка я следующий пост в качестве продолжения прямого пути доказательства...
Исследование ряда Фибоначчи (продолжение) Cмотря на формулу 5, мы можем прийти к некоторым выводам асимптотического характера. А именно, если мы будем рассматривать отношение `alpha_k=phi_(k+1)/phi_k` , то оно как раз будет стремиться к пределу `alpha` . Более явно: 6) `alpha=lim_(k->oo) (phi_(k+1))/(phi_k) = (phi_k+sqrt(5*phi_k^2+4*(-1)^k))/(2*phi_k) = lim_(k->oo) (1+sqrt(5+(4*(-1)^k)/(phi_k^2)))/2=(1+sqrt(5))/2` .
Повнимательнее присмотримся к 3.1... Мы видели, что эта формула дала нам формулу 5 при использовании начального условия. Теперь представим, что при неизменном `k` мы будем увеличивать `n` до бесконечности. Тогда 3.1 становится немного неудобной... Мы можем переписать её в виде: 3.2) `phi_(k)*(phi_(n+k+1))/(phi_n) - phi_(k+1)*(phi_(n+k))/(phi_n) + (-1)^k = 0` .
Теперь мы видим, что если в 3.2 `n->oo`, то для получения информативного результата нам необходимо вычислить такой предел: 7) `beta_k = lim_(n->oo) (phi_(n+k))/(phi_n) = lim_(n->oo) (phi_(n+k))/(phi_(n+k-1))*(phi_(n+k-1))/(phi_(n)) = alpha* lim_(n->oo) (phi_(n+k-1))/(phi_(n))=alpha*beta_(k-1)=alpha^2*beta_(k-2)=...=alpha^(k-1)*beta_1 = alpha^k`.
Пользуясь полученным в 7 результатом, и используя 3.2 имеем: `phi_k*alpha^(k+1) - phi_(k+1)*alpha^k + (-1)^k=0` или 8) `phi_(k+1) = phi_k*alpha + ((-1)^k)/(alpha^k)` .
Теперь используем 5: `(phi_k + sqrt(5*phi_k^2 + 4*(-1)^k))/2 = (phi_k + phi_k*sqrt(5))/2 + (- 1/alpha)^k` или 9) `sqrt(5*phi_k^2+4*(-1)^k) = phi_k*sqrt(5) + 2*(- 1/alpha)^k` . Возводя левую и правую части 9 в квадрат (а мы не получим лишних корней, так как последнее слагаемое всегда меньше `phi_k*sqrt(5)` ), получим: `4*(-1)^k = 4*(- 1/alpha)^k*sqrt(5)*phi_k + 4*(- 1/alpha)^(2*k)` или, упрощая: `phi_k = 1/sqrt(5) * (alpha^k - ( - 1/alpha)^k) = 1/sqrt(5)*(((1+sqrt(5))/(2))^k - ((1-sqrt(5))/(2))^k)` . Окончательно: 10) `phi_k = 1/sqrt(5)*(((1+sqrt(5))/(2))^k - ((1-sqrt(5))/(2))^k)` . Это первый путь доказательства - прямой.
Продолжение. Мы видим, что последовательность Фибоначчи связана с... пятиугольником. А ещё с некоторым квадратным уравнением. Посмотрим, с каким... `x^2=x^1+1` . Да, действительно, у этого уравнения есть два корня: `r_1=(1+sqrt(5))/2`, `r_2=(1-sqrt(5))/2` . И что же из этого следует? - спросите Вы
Согласен с Вами, zaq12, получается красиво... Определение 1: последовательность `f_0,f_1,...,f_m,...` будем называть возвратной последовательностью, если для любого `n`: `f_(n+k)=a_(k-1)*f_(n+k-1) + a_(k-2)*f_(n+k-2)+...+a_0*f_n` , а число `k` будем называть порядком возвратной последовательности.
Очевидно, что последовательность Фибоначчи - возвратная последовательность порядка 2. Рассмотрим теперь общую последовательность порядка 2: `f_(n+2)=alpha*f_(n+1)+beta*f_(n)=tau_12*f_(n+1)+tau_02*f_n` . Выпишем выражения нескольких первых членов после `f_(n+1)` через `f_(n+1)` и `f_n` : `f_(n+3)=alpha*f_(n+2)+beta*f_(n+1)=alpha*(alpha*f_(n+1)+beta*f_n) + beta*f_(n+1)=(alpha^2+beta)*f_(n+1) + (alpha*beta)*f_n=tau_13*f_(n+1)+tau_03*f_n` , `f_(n+4)=(alpha*tau_13+beta*tau_12)*f_(n+1)+(alpha*tau_03+beta*tau_02)*f_n` , `...` , `f_(n+k+2)=(alpha*tau_(1,k+1)+beta*tau_(1,k))*f_(n+1)+(alpha*tau_(0,k+1)+beta*tau_(0,k))*f_n` .
Определение 2: уравнение `x^k=a_(k-1)*x^(k-1)+...a_1*x^1+a_0` называется характеристическим уравнением последовательности 1.
Рассмотрим, для простоты, уравнение: `x^2=alpha*x^1+beta*x^0` . Пусть оно имеет два различных корня: `x_1,x_2`, тогда для `k`-го корня выполняется: `x_k^3=(alpha*x_k^1+beta*x_k^0)*x_1=alpha*x_k^2+beta*x_k^1=(alpha^2+beta)*x_k^1+(alpha*beta)*x_k^0 = tau_13*x_k^1+tau_03*x_k^0` . `x_k^(n+2)=alpha*x_k^(n+1)+alpha*x_k^n=(alpha*tau_(1,n+1)+beta*tau_(1,n))*x_k^1+(alpha*tau_(0,n+1)+beta*tau_(0,n))*x_k^0=tau_(1,n+2)*x_k^(1)+tau_(0,n+2)*x_k^0` . Значит: `([x_1^1, x_1^0],[x_2^1,x_2^0])*([tau_(1,n+2)],[tau_(0,n+2)])=([x_1^(n+2)], [x_2^(n+2)])` . Откуда получаем: `([tau_(1,n+2)],[tau_(0,n+2)])=1/(x_1-x_2)*([x_1^(n+2)-x_2^(n+2)],[-x_1*x_2*(x_1^(n+1)-x_2^(n+1))])` . А значит: `f_(n+2)=(f_1-x_2*f_0)/(x_1-x_2)*x_1^(n+2) - (f_1-x_1*f_0)/(x_1-x_2)*x_2^(n+2)` . Мы видим, что общая формула для получения всех членов последовательности, поэтому, будет: `f_n=lambda_1*x_1^n+lambda_2*x_2^n` . Учитывая то, что начальные условия должны выполняться, получаем такую формулу для нахождения неизвестных коэффициентов: `( [lambda_1], [lambda_2] )=( [x_1^1,x_2^1], [x_1^0,x_2^0])^(-1)*([f_1], [f_0])` . Обобщая результаты, хочется опередить вывод Мёбиуса (ведь это не он)... А выводы получаются такие. Для возвратной последовательности порядка `k` мы получаем следующую формулу: `f_n=sum_(i=1)^k lambda_i*x_i^n` . Эта формула действительна, только если все корни характеристического уравнения различны и имеют кратность 1. Мы можем записать её и в матричном виде: `f_n=(x_1^n,x_2^n,...,x_k^n)*([x_1^(k-1),x_2^(k-1),...,x_k^(k-1)],[x_1^(k-2),x_2^(k-2),...,x_k^(k-2)],[...,...,...,...],[1,1,...,1])^(-1)*([f_(k-1)],[f_(k-2)],[...],[f_0])` .
Вывод Мёбиуса Пусть есть числовая последовательность `F: f_k` . Генерирующей функцией этой последовательности мы будем называть функцию: (1) `G(z)=sum_(k=0)^(oo) f_k*z^k` . Очевидно, эта функция будет сходящимся рядом только для некоторой области `D` комплексной плосткости `CC` . Вид этой области зависит от вида последовательности `F` . Пусть последовательность `F` - возвратная последовательность порядка `k` . Образуем произведения: `z^0*G(z)=f_0+f_1*z^0+...+f_(n+k)*z^(n+k)+...` , `z^1*G(z)=0*z^0+f_0*z^1+...+f_(n+k-1)*z^(n+k)+...` , `...` , `z^(k-1)*G(z)=0*z^0+0*z^1+...+f_(1)*z^(n+k)+...` `z^k*G(z)=0*z^0+0*z^1+...+f_(0)*z^(n+k)+...` Значит, `(z^0-a_(k-1)*z^1-...-a_0*z^k)*G(z)=(1,-1,...,-1,-1)*([f_0, f_1, ..., f_(k-1)],[0,f_0,...,f_(k-2)],[...,...,...,...],[0,0,...,f_1],[0,0,...,f_0])*([z^0], [z^1], [...], [z^(k-2)], [z^(k-1)])` . Из этого получим, что: (2) `G(z)=(Q_(k-1)(z))/(P_k(z))` , где `P_k(z)=z^0-a_(k-1)*z^1-...-a_0*z^k` - характеристический полином возвратной последовательности `F` . Из теоремы о разложении правильном отношения полиномов мы знаем, что оно представимо в виде: (3) `G(z)=sum_(i=1)^k sum_(j=1)^(mu_k)A_(ij)/((z-z_i)^j)` , где `mu_k` - кратность `k` -го корня характеристического уравнения. С другой стороны, используя формулу (1) мы получим, что: (4) `f_n=1/(n!)*(d^n)/(dx^n)G(0) = 1/(n!)*sum_(i=1)^k sum_(j=1)^(mu_k) (A_(ij)*(-1)^n*(n+j)!)/(j!*(z-z_i)^(n+j))|_(z=0) = sum_(i=1)^k sum_(j=1)^(mu_k) ((n+j)!)/(n!*j!)*(-1)^n*A_(ij)/((z-z_i)^(n+j))|_(z=0) = sum_(i=1)^k sum_(j=1)^(mu_k) ((n+j)!)/(n!*j!)*((-1)^j*A_(ij))/(z_i^(n+j))` . Учтя, что корень характеристического полинома обратный к корню характеристического полинома, образованного в предыдущем посте: `z_i=1/x_i` , мы получим следующую формулу: (5) `f_n=sum_(i=1)^k sum_(j=1)^(mu_k) ((n+j)!)/(n!*j!)*(-1)^j*A_(ij)*x_i^(n+j)` , пригодную уже для любой возвратной последовательности, пусть даже с кратными корнями характеристического уравнения.
По возвратным последовательностям есть довольно интересные книги: А.И.Маркушевич. Возвратные последовательности. "Популярные лекции по математике", Выпуск 1. Н.Н.Воробьёв. Числа Фибоначчи. "Популярные лекции по математике", Выпуск 6.
Асимптотическое поведение ряда Фибоначчи и быстрое вычисление на компьютере
Как видим, второй корень характеристического уравнения последовательности Фибоначчи по модулю меньше единицы: `|alpha_2|=|(1-sqrt(5))/2|<1` . Значит, так как первый корень по модулю больше единицы, мы получим асимптотическую формулу для ряда Фибоначчи при больших `n` : `f_n~1/sqrt(5)*((1+sqrt(5))/2)^n` . Если же учесть, что все члены последовательности - целые числа, то можем заключить, что точное значение из асимптотической формулы мы получим, округляя результат к ближайшему целому числу: `f_n=round(1/sqrt(5)*((1+sqrt(5))/2)^n)` . Этой формулой очень удобно пользоваться при вычислении ряда на компьютере.
Возвратные последовательности и решения полиномиальных уравнений
Затронув темы о полиномах и нахождении их решений, мы можем также указать на прямую связь алгебры полиномов с возвратными последовательностями. Можно показать, что все периодические последовательности чисел также являются возвратными. Доказательство этого просто: Пусть периодическая часть последовательности будет `x_0, x_1,..., x_(m-1)`, тогда можем записать: 1) `x_m=0*x_(m-1) + 0*x_(m-2)+...+0*x_1+1*x_0` и так далее. Обобщая, получим: 2) `x_k = x_(k-m)` . В этом случае решением характеристического уравнения 3) `q^m=1` очевидно будут все корни степени `m` из единицы. Пусть теперь у нас есть первообразный корень из единицы - `epsilon` . Тогда его степени будут пробегать все решения уравнения (3) в некотором порядке. Поэтому, общее решение будет представляться следующим образом: 4) `x_k = alpha_(0*k)*epsilon^(0*k)+alpha_1*epsilon^(1*k)+...+alpha_(m-1)*epsilon^((m-1)*k)` .
Заметим, что если в качестве последовательности выбрать все корни некоторого уравнения 5) `P_m(x)= beta_(m)*x^m + ... + beta_0*x^0` . перечисляя их в произвольном но установленном порядке, то мы тоже получим периодическую последовательность. Эта периодическая последовательность корней будет перечислять все из них и к тому же все коэффициенты `alpha_t` будут функциями от коэффициентов уравнения: `alpha_t = alpha_t(beta_0, beta_1, ... , beta_m)`. Дальнейший анализ этих функций и приведёт к резольвентам Лагранжа, ведь по сути 4) это и есть резольвентное уравнение. Остаётся только узнать какая функция ведёт перечисление всех корней уравнения по одному разу и изучить свойства этой функции. Чем мы и займёмся... Если Вы, конечно, не против
P.S.: почему в этой теме - а ведь она натолкнула нас на идею резольвент.
Главная / Форум
Правила
Правила форума
Формулы
Задачи
ГДЗ
Анимации
Программы
Обратная связь
Каталог сайтов
Карта сайта
Онлайн-компьютер
