Регистрирайте сеРегистрирайте се

Линейно-рекурентни...


 
   Форум за математика Форуми -> Олимпиади и състезания за 9-12 клас
Предишната тема :: Следващата тема  
Автор Съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Sun Jul 12, 2009 6:36 pm    Заглавие: Линейно-рекурентни...

Нека [tex]c[/tex] е положително цяло число. Редицата [tex]\{\math{f}_n\}[/tex] е дефинирана както следва:
[tex]\math{f}_1=1[/tex], [tex]\math{f}_2=c[/tex], [tex]\math{f}_{n+1}=2\math{f}_n-\math{f}_{n-1}+2[/tex] [tex]\left(n\ge 2\right)[/tex].
Докажете, че за всяко [tex]k\in\mathbb{N}[/tex], съществува [tex]r\in\mathbb{N}[/tex], такова че [tex]\math{f}_{k}\math{f}_{k+1}=\math{f}_{r}[/tex].

И две допълнения от мен:
a) може ли [tex]c[/tex] да не бъде цяло;
б) може ли [tex]c[/tex] да не бъде положително?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
martin.nikolov
Напреднал


Регистриран на: 22 Apr 2009
Мнения: 489

Репутация: 35.5Репутация: 35.5Репутация: 35.5Репутация: 35.5
гласове: 21

МнениеПуснато на: Mon Jul 13, 2009 6:51 pm    Заглавие:

Предполагам, че има интересно хитро решение. Аз не можах да измисля нищо и затова го направих с директни сметки.

За общия член се получава: [tex]f_n=n^2+(c-4)n+(4-c)[/tex]. От тук при дадено k заместваме и решаваме относно r. Получава се [tex]r=k^2+(c-3)k+(4-c)[/tex]. От тук е ясно, че c трябва да е цяло. Ако не е положително, твърдението няма да е вярно за всяко k, а от дадено цяло число нататък.

Може да сеъм сбъркал някъде в сметките.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Mon Jul 13, 2009 7:23 pm    Заглавие:

Да, има възможност да съществува някакво комбинаторно решение. Иначе и аз го решавам почти като теб. Решението във файла, от който го взех е същото (в общи линии).
А относно б) от въпроса ми, отговорът (поне така както аз го решавам) е положителен! Естествено, с тази формула, която си написал, при някои отрицателни [tex]c[/tex], индекса е отрицателен. Но това може, така да се каже, да се заобиколи!
Иначе самата задача е от съкратения списък за МОМ 1984!
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martin.nikolov
Напреднал


Регистриран на: 22 Apr 2009
Мнения: 489

Репутация: 35.5Репутация: 35.5Репутация: 35.5Репутация: 35.5
гласове: 21

МнениеПуснато на: Mon Jul 13, 2009 7:29 pm    Заглавие:

Жалко, понеже беше очевидно, че задачата е олимпииска аз се надявах да има кефещо тарикатско решение без сметки. За положителното или отрицателно съм съгласен, в зависимост от тълкуването може да се приеме.

Иначе за сметките, аз първо намерих общия член по стандартния начин и чак после видях, че може и без да се знае как се решават линейни рекурентни редици.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Mon Jul 13, 2009 7:45 pm    Заглавие:

martin.nikolov написа:
За положителното или отрицателно съм съгласен, в зависимост от тълкуването може да се приеме.

Може ли да кажеш какво точно имаш предвид. Защото мисля, че не е това, което аз имам.
martin.nikolov написа:
Иначе за сметките, аз първо намерих общия член по стандартния начин и чак после видях, че може и без да се знае как се решават линейни рекурентни редици.

Става ли да покажеш как? С индукция ли?

Иначе това, че не е публикувано комбинаторно решение, не отхвърля съществуването му. Такива решения, често са доста трудни за откриване. Честно казано на състезание, ако ми се падне такава задача, в началото ще реша да си изкарам сигурен максимален брой на нея, отколкото несигурен такъв, макар възможност за специална награда (искам да кажа, че ще тръгна по алгебричен път (бил той и грозен, и хамалски), вместо да бродя в дебрите на комбинаториката с цел (неизвестно дали въобще съществува) красиво решение).
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martin.nikolov
Напреднал


Регистриран на: 22 Apr 2009
Мнения: 489

Репутация: 35.5Репутация: 35.5Репутация: 35.5Репутация: 35.5
гласове: 21

МнениеПуснато на: Mon Jul 13, 2009 8:16 pm    Заглавие:

MM написа:
martin.nikolov написа:
За положителното или отрицателно съм съгласен, в зависимост от тълкуването може да се приеме.

Цитат:

Може ли да кажеш какво точно имаш предвид. Защото мисля, че не е това, което аз имам.



Не, аз просто се съгласявах, че индекса ще е отрицателен в някой случай.

Цитат:

martin.nikolov написа:
Иначе за сметките, аз първо намерих общия член по стандартния начин и чак после видях, че може и без да се знае как се решават линейни рекурентни редици.

Става ли да покажеш как? С индукция ли?


Записваш го така [tex]f_{n+1}-f_n=f_n-f_{n-1}+2[/tex], полагаш [tex]a_n=f_{n+1}-f_n[/tex]. Това е аритметична прогресия, за която се знае първия член и разликата. Следователно може да се сметне сумата

[tex]S_n=a_1+\cdots+a_n=(f_2-f_1)+(f_3-f_2)+(f_4-f_3)+\cdots+(f_{n+1}-f_n)=f_{n+1}-f_1[/tex]



Цитат:

Иначе това, че не е публикувано комбинаторно решение, не отхвърля съществуването му. Такива решения, често са доста трудни за откриване. Честно казано на състезание, ако ми се падне такава задача, в началото ще реша да си изкарам сигурен максимален брой на нея, отколкото несигурен такъв, макар възможност за специална награда (искам да кажа, че ще тръгна по алгебричен път (бил той и грозен, и хамалски), вместо да бродя в дебрите на комбинаториката с цел (неизвестно дали въобще съществува) красиво решение).


Да, не се изразих правилно. Надявах се да ти е известно за да го постнеш. Иначе е ясно, че дори на никой да не е извесно не значе че го няма. Пък и стандартните методи трябва да се знаят, и да се изпозват.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Mon Jul 13, 2009 9:43 pm    Заглавие:

martin.nikolov написа:

Записваш го така [tex]f_{n+1}-f_n=f_n-f_{n-1}+2[/tex], полагаш [tex]a_n=f_{n+1}-f_n[/tex]. Това е аритметична прогресия, за която се знае първия член и разликата. Следователно може да се сметне сумата

[tex]S_n=a_1+\cdots+a_n=(f_2-f_1)+(f_3-f_2)+(f_4-f_3)+\cdots+(f_{n+1}-f_n)=f_{n+1}-f_1[/tex]

А ти от това директно общия член ли намираш или правиш някаква друга врътка.
Ако може покажи!

А иначе ето до какво друг стигнах.
Взимаме [tex]c\le 0[/tex]. Получаваме още [tex]\left(n^2+\left(c-4\right)n+4-c\right)\left(\left(n+1\right)^2+\left(c-4\right)\left(n+1\right)+4-c\right)=\left(-n^2+\left(3-c\right)n\right)^2+\left(c-4\right)\left(-n^2+\left(3-c\right)n\right)+4-c[/tex]
Значи имаме [tex]f_{n}f_{n+1}=f_{-n^2+\left(3-c\right)n}[/tex], за което естествено трябва [tex]-n^2+\left(3-c\right)n>0[/tex]. Последното е вярно за [tex]n\in \left(0,3-c\right)[/tex]. Също така имаме, че ни трябва [tex]n^2+\left(c-3\right)+c-4>0[/tex]. Последното е вярно за всички [tex]n[/tex] извън интервала [tex]\left(-\frac{sqrt{c^2-2c-7}+c-3}{2},\frac{sqrt{c^2-2c-7}-c+3}{2}\right) [/tex] (Ако дискриминантата е отрицателна нямаме проблем с положителността). Лесно се проверява, че последния интервал е подинтервал на по-горния. Така ако за някое [tex]n[/tex] имаме проблем с единия индекс, то няма да имаме с другия и ще вземем него (под "проблем" разбирам отрицателност). Значи за всяко [tex]c[/tex] нямаме противоречие с това, което се иска да се докаже в задачата.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martin.nikolov
Напреднал


Регистриран на: 22 Apr 2009
Мнения: 489

Репутация: 35.5Репутация: 35.5Репутация: 35.5Репутация: 35.5
гласове: 21

МнениеПуснато на: Mon Jul 13, 2009 10:43 pm    Заглавие:

MM написа:
martin.nikolov написа:

Записваш го така [tex]f_{n+1}-f_n=f_n-f_{n-1}+2[/tex], полагаш [tex]a_n=f_{n+1}-f_n[/tex]. Това е аритметична прогресия, за която се знае първия член и разликата. Следователно може да се сметне сумата

[tex]S_n=a_1+\cdots+a_n=(f_2-f_1)+(f_3-f_2)+(f_4-f_3)+\cdots+(f_{n+1}-f_n)=f_{n+1}-f_1[/tex]

А ти от това директно общия член ли намираш или правиш някаква друга врътка.
Ако може покажи!



Ами от тук [tex]f_{n+1}=S_n+f_1[/tex]. А [tex] S_n[/tex] е сумата на аритметична прогресия с разлика 2 и първи член c-1.

Да, за останалото аз бях решил, че индекса ще е отрицателен в някой случай и не го смятах.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Saposto_MM
Напреднал


Регистриран на: 02 Apr 2007
Мнения: 383
Местожителство: Панагюрище
Репутация: 124.4
гласове: 67

МнениеПуснато на: Tue Jul 14, 2009 9:35 am    Заглавие:

Извинявай, всичко е ясно просто бях използвал неправилната формула за аритметична прогресия и не ми се получаваха нещата (утрото е по-мъдро от вечерта).
Иначе добре си го направил. Аз съвсем наскоро се запознах с теория около тези редици и веднага я прилагах, не съм се замислял за друг начин ("знанията понякога ограничават ума" - теория, която подкрепям).
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Олимпиади и състезания за 9-12 клас Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
Може да прикачвате файлове
Може да сваляте файлове от този форум
Copyright © 2005-2020 math10.com.