1 Востаннє редагувалося Betterthanyou (17.07.2016 19:23:57)

Тема: Дискретна математика. Знайти формулу загального члена послідовності

Послідовність задана рекурентним співвідношенням. Знайти формулу загального члена цієї послідовності.
http://replace.org.ua/misc.php?action=pun_attachment&item=1326&download=0
Я читав про послідовності, але не зрозумів.
Ось я спробував порахувати послідовність від а1 до а12 і в мене вийшло ось таке

3 4 -4 -24 -32 32 192 256 -256 -1536 -2048 2048

a1 = 3
an+1 = 4
2 * 4 = 8
4 * 3 = 12
8 - 12 = -4
a2 = -4

a2 = 4
an+1 = -4
2 * -4 = -8
4 * 4 = 16
-8 - 16 = -24
a2 = -24

a3 = -4
an+1 = -24
2 * -24 = -48
4 * -4 = -16
-48 - -16 = -32
a2 = -32

a4 = -24
an+1 = -32
2 * -32 = -64
4 * -24 = -96
-64 - -96 = 32
a2 = 32

a5 = -32
an+1 = 32
2 * 32 = 64
4 * -32 = -128
64 - -128 = 192
a2 = 192

a6 = 32
an+1 = 192
2 * 192 = 384
4 * 32 = 128
384 - 128 = 256
a2 = 256

a7 = 192
an+1 = 256
2 * 256 = 512
4 * 192 = 768
512 - 768 = -256
a2 = -256

a8 = 256
an+1 = -256
2 * -256 = -512
4 * 256 = 1024
-512 - 1024 = -1536
a2 = -1536

a9 = -256
an+1 = -1536
2 * -1536 = -3072
4 * -256 = -1024
-3072 - -1024 = -2048
a2 = -2048

a10 = -1536
an+1 = -2048
2 * -2048 = -4096
4 * -1536 = -6144
-4096 - -6144 = 2048
a2 = 2048

Я правильно порахував ?
Як знайти загальну формулу ? (Знайти формулу загального члена цієї послідовності)

Post's attachments

Untitled.png 4.11 kb, 32 downloads since 2016-07-17 

Подякували: leofun011

2

Re: Дискретна математика. Знайти формулу загального члена послідовності

теж цікаво, як таке шукається

тут спілкуються українці (серед них є програмісти)
https://discord.gg/Zk29v4P

3 Востаннє редагувалося koala (17.07.2016 22:40:54)

Re: Дискретна математика. Знайти формулу загального члена послідовності

Наведу 20 елементів послідовності:

3 4 -4 -24 -32 32 192 256 -256 -1536 -2048 2048 12288 16384 -16384 -98304 -131072 131072 786432 1048576

розрахунки

def an(n):
    if n==1:
        return 3
    if n==2:
        return 4
    return 2*an(n-1)-4*an(n-2)
for i in range(1,21):
    print(an(i),end=' ')

Що я тут бачу? По множниках:
3 4 (-1)*4 (-1)*2*3*4 (-1)*2*4^2 2*4^2 3*4^3 4^4 (-1)*4^4 (-1)*2*3*4^4 (-1)*4^5 4^5 і поки досить.
-1 повторюється в кожній другій трійці, починаючи з 3-го елемента. Прибираємо, щоб далі не заважала:
3 4 4 2*3*4 2*4^2 2*4^2 3*4^3 4^4 4^4 2*3*4^4 2*4^5 2*4^5
3 повторюється в кожному 3-му елементі, починаючи з 1-го. Прибираємо і переводимо в степені 2:
1 2^2 2^2 2^3 2^5 2^5 2^6 2^8 2^8 2^9 2^11 2^11
Степені:
0 2 2 3 5 5 6 8 8 9 11 11.
Це майже лінійна формула, тільки кожен 3-й елемент, починаючи з 2-го, більший на 1.
Ніби все. Тепер клепаємо формулу. Зараз голова не варить, тому буду робити це брудно, нехорошими функціями. Ліньки думати, чи можна хорошими.
(-1)^[n/3], де [] - ціла частина числа, буде давати 1 при 1,2,6,7,8,12... і -1 при решті.
3-2*sign((n-1) mod 3), де sign - знак (1 для додатних, -1 для від'ємних, 0 для нуля), mod - остача від ділення буде давати 3 при n=1,4,7,... і 1 при решті.
n-sign((n+1) mod 3) буде давати послідовність 0, 2, 2...
Отже,
f(n)=(-1)^[n/3]*(3-2*sign((n-1) mod 3))*2^(n-sign((n+1) mod 3))
виглядає доволі схожим на шукану формулу. Спробуємо довести, що це вона. База індукції:

f(1)=(-1)^[1/3]*(3-2*sign((1-1) mod 3))*2^(1-sign((1+1) mod 3))=
=(-1)^0 * (3-2*sign(0))*2^(1-sign(2))=3*2^0=3
f(2)=(-1)^[2/3]*(3-2*sign((2-1) mod 3))*2^(2-sign((2+1) mod 3))=
=(-1)^0 * (3-2*sign(1))*2^(2-sign(0))=2^2=4

Перехід: довести, що
f(n)=2f(n-1)-4f(n-2)
Спробуйте зробити це самостійно, але я б дав 90%, що це вдасться розглядом 3 випадків: n=3l, n=3l+1 і n=3l+2.

4

Re: Дискретна математика. Знайти формулу загального члена послідовності

Дивимося уважно рекурентне співвідношення в умові:

a(n+2) = 2a(n+1) - 4a(n)

і

koala написав:

f(n)=2f(n-1)-4f(n-2)

Нічого не нагадує? Пане koala, як то Ви не полінувалися написати аж стільки тексту?
Звісно, є задачі, де не буде все так просто, але Я б при пошуку розвязку відштовхувався б саме від рекурентного співвідношення, а не пошуку членів послідовності.

Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/

5 Востаннє редагувалося koala (18.07.2016 12:13:55)

Re: Дискретна математика. Знайти формулу загального члена послідовності

Master_Sergius написав:

Нічого не нагадує?

*FACEPALM*
Ви про математичну індукцію хоч щось чули?

Master_Sergius написав:

Пане koala, як то Ви не полінувалися написати аж стільки тексту?

Це не розв'язок і тим більше не його чистовик. Це хід розв'язку, як він у мене йшов... ну хіба що пару невдалих шляхів відкинув під час написання.

Master_Sergius написав:

Звісно, є задачі, де не буде все так просто, але Я б при пошуку розвязку відштовхувався б саме від рекурентного співвідношення, а не пошуку членів послідовності.

*FACEPALM* *FACEPALM* *FACEPALM*

6

Re: Дискретна математика. Знайти формулу загального члена послідовності

Я просто подумав, чи є сенс доводити ту останню формулу, якщо вона є тим же представленням, що в умові, але вже аж потім до мене дійшло :)
Понеділок - день важкий.

Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/

7 Востаннє редагувалося Betterthanyou (18.07.2016 16:39:17)

Re: Дискретна математика. Знайти формулу загального члена послідовності

Так формула працює (результат у файлі бо на форумі переноситься розрахунок та стає не зрозумілим)
Завантажити

код

#include <iostream>

int sign(int n)
{
    int sign(0);
    if (n > 0)
        sign = 1;
    else if (n < 0)
        sign = -1;
    return sign;
}

int f(int n)
{
    return pow ((-1), (n / 3)) * (3 - 2 * sign((n - 1) % 3)) *
           pow(2 , (n - sign((n + 1) % 3)));
}

int main()
{
    for (int i = 1; i <= 20; i++)
        std::cout << f(i) << " ";

    std::cout << std::endl;
    system("pause");
    return 0;
}

А можна якось автоматизувати процес знаходження формули (написати програму) ?

Закинув ще приклади, тут їх багато не хотілося б шукати формулу в ручну

http://s8.hostingkartinok.com/uploads/images/2016/07/96f52443ecf542f0a0bbef945eb0fed7.png
Post's attachments

file.txt 6.73 kb, 65 downloads since 2016-07-18 

Подякували: leofun011

8 Востаннє редагувалося koala (18.07.2016 16:36:02)

Re: Дискретна математика. Знайти формулу загального члена послідовності

Довести все одно треба - ви не можете знати, чи не "зламається" формула на 101-му елементі, доки цього не зробите.
Що ж стосується програми, яка б "знаходила формулу" - то тут все робиться так само, як і в будь-якому іншому випадку: спершу розв'язуєте задачу в загальному вигляді (дано: a1, a2, an+2=x*an+1-y*an, знайти f(n)=an), а потім програмуєте.

Подякували: leofun01, Betterthanyou2

9 Востаннє редагувалося leofun01 (19.07.2016 16:53:47)

Re: Дискретна математика. Знайти формулу загального члена послідовності

Як математик, висловлю і я свою компетентну думку.
Почну з того, що конкретно в даному випадку все набагато простіше:
Якщо an+2 = 2*an+1 - 4*an, то
an+3 = 2*an+2 - 4*an+1.
Замість an+2 підставимо початковий вираз, тоді
an+3 = 2*(2*an+1 - 4*an) - 4*an+1;
an+3 = 4*an+1 - 8*an - 4*an+1;
an+3 = -8*an.
Отже для цілих значень n достатньо 3-х початкових елементів (наприклад: 3, 4, -4; хоча підійдуть і інші).
В функції (в програмі) можна спочатку робити перевірку остачі від ділення n на 3 [switch(n % 3) case 0; case 1; case 2;] і присвоювати відповідне початкове значення, а потім множити на (-8) в степені ([n / 3] - 1) (це якщо для { 3, 4, -4 }).
Також можна зробити узагальнення (аналітичне продовження) для комплексних значень n.

upd: короче koala зробив усе правильно, просто мене трохи налякали sign'и.

Подякували: Betterthanyou1

10 Востаннє редагувалося leofun01 (19.07.2016 16:50:18)

Re: Дискретна математика. Знайти формулу загального члена послідовності

Betterthanyou написав:

А можна якось автоматизувати процес знаходження формули (написати програму) ?

Звичайно що можна.

Нагадало дипломну

В мене дипломна робота була по автоматизації знаходження формул. Конкретно по знаходженню довільних співвідношень для гіпергеометричної функції Гауса (2F1 / Hypergeometric2F1) і побудові неперервних ланцюгових дробів на основі отриманих співвідношень в загальній формі. Вдалося створити програму, яка то все знаходила.

Впевнений у вас получиться створити таку програму.
По ідеї можна навіть створювати програми, які доводять теореми (мається на увазі аналітично, а не тільки на основі обробки великих даних).

Betterthanyou написав:
Закинув ще приклади, тут їх багато не хотілося б шукати формулу в ручну

http://s8.hostingkartinok.com/uploads/images/2016/07/96f52443ecf542f0a0bbef945eb0fed7.png

На якій мові програмування робити програму ? (мені просто самому стало цікаво).

Подякували: Betterthanyou1

11

Re: Дискретна математика. Знайти формулу загального члена послідовності

Прихований текст

Betterthanyou написав:
Закинув ще приклади, тут їх багато не хотілося б шукати формулу в ручну

http://s8.hostingkartinok.com/uploads/images/2016/07/96f52443ecf542f0a0bbef945eb0fed7.png

Betterthanyou написав:

На якій мові програмування робити програму ? (мені просто самому стало цікаво).

С++ або С#

Подякували: leofun011

12 Востаннє редагувалося leofun01 (22.07.2016 13:03:53)

Re: Дискретна математика. Знайти формулу загального члена послідовності

Виявилося це не так просто, як я собі думав. Крім того я погано шукав, загальна формула вже давно знайдена і виглядає отак:
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/NumberedEquation2.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline38.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline39.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline40.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline41.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline42.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline43.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline44.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline45.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline46.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline47.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline48.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline49.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline50.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline51.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline52.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline53.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline54.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline55.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline56.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline57.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline58.gif

http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline59.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline60.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline61.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline62.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline63.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline64.gif

Джерело

Post's attachments

RecurentSeq.zip 26.9 kb, 52 downloads since 2016-07-22 

Подякували: koala, Betterthanyou2

13

Re: Дискретна математика. Знайти формулу загального члена послідовності

Прихований текст

leofun01 написав:

Виявилося це не так просто, як я собі думав. Крім того я погано шукав, загальна формула вже давно знайдена і виглядає отак:
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/NumberedEquation2.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline38.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline39.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline40.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline41.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline42.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline43.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline44.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline45.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline46.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline47.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline48.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline49.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline50.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline51.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline52.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline53.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline54.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline55.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline56.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline57.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline58.gif

http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline59.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline60.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline61.gif
http://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline62.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline63.gifhttp://mathworld.wolfram.com/images/equations/LinearRecurrenceEquation/Inline64.gif

Джерело

Я сьогодні якраз здав екзамен, але нажаль він був на 8 год. і я не побачив цієї формули, нічого буде на майбутнє