Последовательность чисел a[n] назовем линейно-рекуррентной последовательностью, если для некоторого набора чисел k[1],..,k[m] верно   соотношение для любого элемента последовательности:
a[n]=k[1]*a[n-1]+k[2]*a[n-2]+..+k[m]*a[n-m]
Имеется две линейно-рекуррентные последовательности a[n] и b[n]. Будет ли последовательность c[n]=a[n]+b[n] линейно-рекуррентной?

голова заболела...

Линейной - да.
рекуррентной - вроде бы нет.

(0) будет

(2) что такое "линейная" последовательность?

(3) доказательство есть?

(5) ага

(0) Есть мнение, что не будет линейно-рекуррентной

(4) степень каждого члена = 1

(5) см. (1)

(8) не понял?!

Ну вот для затравки пример
a[n]=2*a[n-1]-a[n-2]
1,2,3,4,5,...
b[n]=2*b[n-1]
1,2,4,8,16,...
их сумма:
2,4,7,12,21...
удовлетворяет формуле
c[n]=2*c[n-1]-c[n-2]+c[n-3]

Вам чего, ,kznm, заняться нечем?

+(11) наврал ((

если они линейно рекуррентные с одним и тем же m, то все понятно. складываем формулы и приехали
если с разными, то надо сделать следующее
берем ту последовательность, которая линейно-рекуррентная с меньшим m1 (назовем это число периодом зависимости).
a[n]=k[1]*a[n-1]+k[2]*a[n-2]+..+k[m1]*a[n-m1]
подставляем сюда a[n-1]=k[1]*a[n-2]+k[2]*a[n-3]+..+k[m1]*a[n-m1-1]
получаем, что эта последовательность также является линейно-рекуррентной и с "периодом зависимости" m1+1
последовательным применением сией процедуры осознаем, что она является линейно-рекуррентной с любым периодом зависимости, большим m1, в том числе и с m2 (периодом зависимости второй последовательности). дальше опять простым сложением

(14) "если они линейно рекуррентные с одним и тем же m, то все понятно. складываем формулы и приехали"
куда приехали? вот для примера из 11 найди формулу для суммы последовательностей

(11)(13) Если этот пример не получается, значит ты нашел хотя бы две последовательности, которые не удовлетворяют заданным условиям. Значит сумма последовательностей не будет рекуррентной, не?

(16) нет доказательства, что этот пример не получается, пока это лишь неудачная попытка

(15) а, ну да, значит я тоже наврал )))

a[n]=k*a[n-1]
b[n]=k'*b[n-1]
a[n] + b[n] = k*a[n-1]+k'*b[n-1]
Как из последнего равенства получить выражение k''(a[n-1]+b[n-1]) я не понимаю)

исправление (11), формула такая:
c[n]=4*c[n-1]-5*c[n-2]+2*c[n-3]

(19) Глупость какую-то написал)

Наверное, так:
-производящая функция каждой - рациональная;
-производящая функция суммы = сумме производящих функций, т.е. сумма 2-х рациональных, т.е. рациональная;
- т.е. производящая функция некоторой последовательности.

Для того, чтобы было удобно писать формулы, определение линейно-рекурентной последовательности перепишем по-другому. Будем считать таковой последовательность чисел
... x[-2],x[-1],x[0],x[1],x[2],... если для некоторого набора чисел a[1],a[2],...a[n] выполняется условие
x[1+q]*a[1]+x[2+q]*a[2]+...x[n+q]*a[n]=0 (1)
при любом целом q. Ясно, что пользуясь (1) последовательность x можно продолжать в обе стороны. То есть зная x[1],x[2],...,x[n] можно вычислить x[q] для любого целого q. Причем q может быть как положительным, так и отрицательным.
Допустим, что у нас есть две таких последовательности
... x[-2],x[-1],x[0],x[1],x[2],...(2)
... y[-2],y[-1],y[0],y[1],y[2],...(3)
Набор коэффициентов для первой последовательности будет
a[1],a[2],...a[n]
набор коэффициентов для второй последовательности будет
b[1],b[2],...b[m]
Покажем, что сумма последовательностей (2) и (3) будет линейно-рекурентной. Определим набор коэффицентов
c[1],c[2],...c[n+m]
по формуле:
c[k]= a[k]*b[1]+a[k-1]*b[2]+...+a[1]*b[k] (4)
Проверим, удовлетворяет ли последовательность (2) условию
x[1+q]*c[1]+x[2+q]*c[2]+...x[n+m+q]*c[n+m]=0
для любого целого q.
Действительно,
x[1+q]*c[1]+x[2+q]*c[2]+...x[n+m+q]*c[n+m]=
=x[1+q]*a[1]*b[1]+x[2+q]*(a[2]*b[1]+a[1]*b[2])+...
+x[i+q](a[i]*b[1]+a[i-1]*b[2]+a[i-2]*b[3]+...+a[1]b[i])+...
+...x[n+m+q]*a[n]*b[m]=
=b[1](a[1]*x[1+q]+a[2]x[2+q]+...+a[n]*x[n+q])+
+b[2](a[1]*x[2+q]+a[2]x[3+q]+...+a[n]*x[1+n+q])+...
...+b[i](a[1]*x[i+q]+a[2]x[i+1+q]+...+a[n]*x[i-1+n+q])+...
...+b[k-1](a[1]*x[k-1+q]+a[2]x[k+q]+...+a[n]*x[k-2+n+q])=0
Аналогично проверяется, что последовательность (3) тоже удовлетворяет условию
x[1+q]*c[1]+x[2+q]*c[2]+...x[n+m+q]*c[n+m]=0
При этом во всех выкладках если имеет место обращение к значениям коэффициентов a[] и b[] к индексам, выходящим за пределы области определения, то коэффициенты считаем равными нулю.
Прежде, чем выложить эти выкладки сюда, я их проделал на бумажке. Здесь отсутствует знак суммирования, что делает выкладки менее понятными. Тем менее, основная идея и ход решения достаточно просты.

И где доказательство, что c[] зависит от своих предыдущих членов?

(23) http://demotivators.to/p/2432/v-samom-dele.htm
=)

(24)Я немного изменил терминологию. В моем решении a[],b[],c[] - это постоянные наборы коэффициентов по определению. То есть a[],b[] заданы изначально, c[]определяется по формуле:
c[k]= a[k]*b[1]+a[k-1]*b[2]+...+a[1]*b[k]
где k - целое число от 1 <= k <= n+m
При этом во всех выкладках если имеет место обращение к значениям коэффициентов a[] и b[] к индексам, выходящим за пределы области определения, то коэффициенты считаем равными нулю.
x[],y[] - рекурентные последовательности

(26)+Если доказать, что x[],y[] являются линейно-рекурентными с набором коэффициентов c[1],c[2],...c[n+m], то тогда и их сумма тоже будет линейно-рекурентной с тем же набором.

(27)ну допустим, покажи как твоя формула работает в (11)

эвона как у вас бодунизм затейливо выходит из организма

(28)
x[]  1,2,3,4,5,...
y[]  1,2,4,8,16,...
z[]  2,4,7,12,21,...
a[]  1,-2,1
b[]  2,-1

c[1] = 1*2 = 2
c[2] = 1*(-1)+(-2)*2 = -5
c[3] = 1*0 + (-2)*(-1) + 1*2 = 4
c[4] = 1*0 + (-2)*0 + 1*(-1) + 0*2 = -1

c[]  2,-5,4,-1
Проверим, что для x[] коэффициенты c[] подходят:
1*2+2*(-5)+3*4+4*(-1)=0
Проверим, что для y[] коэффициенты c[] подходят:
1*2+2*(-5)+4*4+8*(-1)=0
Проверим, что для z[] коэффициенты c[] подходят:
2*2+4*(-5)+7*4+12*(-1)=0

Еще одна проверка для z[]. Начиная со второго члена последовательности:
4*2+7*(-5)+12*4+21*(-1)=0

(29)Не знаю насчет бодунизма. Лично я покопался в этом с удовольствием.

(0) будут, на этом построен вывод игровых денег в онлайн-играх

.. я офигеваю от вашей офигенности..

(34) да ладно, задача настолько примитивна, что я даже не ожидал от ТС

В общем случае, C[N]=A[N]+B[N]=Сумма(K1i*(A[N-i]+B[N-i])+K2i*(A[N-i]-B[N-i]))
Если разность выразить через предыдущие, то получим другие значения у следующих элементов.
Если A[N]=Сумма(Kai*A[N-i]), а B[N]=Сумма(Kbi*B[N-i])
то K1i=(Kai+Kbi)/2, а K2i=(Kai-Kbi)/2
A[N-i]-B[N-i]=Сумм(Kaj*A[N-i-j]-Kbj*B[N-i-j])
То есть следующий коэффициент будет {Ka(i+1)+(Ka(i)-Kb(i))/2*Ka(i)}*A[N-i-1]+{Kb(i+1)+((Ka(i)-Kb(i))/2*Kb(i)}*B[N-i-1]
K1(i+1)=(Ka(i+1)+Kb(i+1)+(Ka(i)-Kb(i))(Ka(i)+Kb(i))/2))/2=
=(Ka(i+1)+Kb(i+1)+(Ka(i)^2-Kb(i)^2)/2)/2
K2(i+1)=(Ka(i+1)-Kb(i+1)+(Ka(i)-Kb(i))(Ka(i)-Kb(i))/2)/2
Ну и так далее.

(23) красиво

несколько слов в продолжение темы
Если рассмотреть две арифметические прогрессии, то есть последовательности, заданные коэффициентами (1,-2,1) (согласно терминологии из (23)), то предложенный там алгоритм дает последовательность, заданную коэффициентами (1, -4, 6, -4, 1). Однако на самом деле множество таких последовательностей шире чем множество сумм арифметических прогрессий, в тоже время, суммой арифметических прогрессий очевидно является снова арифметическая прогрессия, то есть заданная всё теми же (1,-2,1). Получаем, что множество последовательностей вида (1,-2,1) является подмножеством множества вида (1, -4, 6, -4, 1).
Теперь посмотрим на это с другой стороны.
Каждому множеству последовательной с коэффициентами a[0],...,a[n-1] можно сопоставить многочлен f(x)=a[0]*X^(n-1)+...+a[n-1]. Далее просто класс последовательностей f(x).
Тогда:

Утверждение 1. Алгоритм в (23) для двух последовательностей классов f(x) и g(x) строит последовательность класса f(x)*g(x), куда вложены суммы последовательностей классов f(x) и g(x).

Утверждение 2. Если f(x) делится на g(x), то класс последовательностей g(x) содержится в классе f(x).

Предположение. Множеством всевозможных сумм последовательностей классов f(x) и g(x) является класс НОК(f(x),g(x)). НОК - наименьшее общее кратное f(x) и g(x).

Если не ошибаюсь, эти вопросы решаются, если обратиться к производящей функции последовательности. При этом многочлен f[x) будет ее знаменателем. А f[x)*g[x) - знаменателем для суммы, если у f[x) и g[x) нет общих делителей.

из Утверждения 2 в (37) следует, что периодическими последовательностями будут те и только те, которым соответствует делитель x^n-1

нашел старую тему
http://demotivators.to/media/posters/3136/40460491_najdite-10-razlichij.jpg

+(40 палюсь, вот она: ОФФ: Задачка на неделю

(39) Может быть периодические те, у которых характеристический многочлен имеет только вещественные (чисто мнимые) корни?

(42) нет

(39) Для уравнения: X(n)=КОРЕНЬ(2)*X(n-1)-1 последовательность периодическая. Похоже, что для периодической последовательности корни характеристического уравнения это корни из 1 (а длина периода = степени корня).

(44) "Похоже, что для периодической последовательности корни характеристического уравнения это корни из 1"

собственно это и написано в (39)

(45) Виноват: не обратил внимания на "делитель...".