Funkcja rekurencyjna w zależności od parametru "n"

[ktosztlumu]

Witam mam problem znaleźć jaka liczba symboli zostanie zwrócona w zależności od parametru n, wiem, że
dla n=1 zwrócony jest jeden symbol
dla n=2 zwrócone jest 1 + 4 symboli
dla n=3 zwrócone jest 1 + (1+4) + 9

Ogólnie : dla każdego kolejnego n zwracane jest: \(\displaystyle{ \sum_{k=1}^{n-1} a_{k} + n^{2}}\) symboli

Z góry dziękuję za pomoc.

[abc666]

Łatwo zauważyć, że jest to suma kolejnych kwadratów liczb naturalnych. Jak obliczyć taką sumę możesz zobaczyć tutaj 258562.htm

[ktosztlumu]

Czy na pewno jest to suma kolejnych kwadratów liczb naturalnych?

Zauważmy że dla n= 3 mamy : 1 + (1 +4) + 9 = 15
Dla 4 to będzie : 1 + (1+4) + (1+1+4+9) + 16 = 37
Wydaje mi się, że w sumie kwadratów wyszło by dla n=3 , 14 (1+4+9). Jeśli się mylę to proszę mnie poprawić.

[Qń]

Jeśli interesuje Ciebie sam wzór, a nie wyprowadzenie, to:
\(\displaystyle{ a_n=3\cdot 2^n -2n-3}\)

Q.

[abc666]

ktosztlumu, tak masz rację.

[ktosztlumu]

Qń

A mógłbyś udzielić podpowiedzi jak doszedłeś do tego wzoru ?:> tzn z czego skorzystać ?

Z góry dzięki

[Qń]

Mamy zależność:
\(\displaystyle{ a_n=\sum_{k=1}^{n-1} a_{k} + n^{2}}\)
więc także:
\(\displaystyle{ a_{n+1}=\sum_{k=1}^{n} a_{k} + (n+1)^{2}}\)
Jeśli odejmiemy te równości stronami, to dostaniemy po drobnym przekształceniu:
\(\displaystyle{ a_{n+1}=2a_n+2n+1}\)

To zaś już jest zwykła liniowa rekurencja, na której rozwiązanie jest wiele sposobów: funkcje tworzące, metoda przewidywań, metoda repertuaru, czynnik sumacyjny czy ręczne przekształcanie.

Q.

[ktosztlumu]

Czy ktoś mógłby mnie oświecić czy moje rozumowanie jest poprawne:

\(\displaystyle{ a_{n+1}=2a_n+2n+1}\)
odpowiednio podstawiam :
za :
\(\displaystyle{ b = 2\\
a = a_{1} =1\\
c = 2n +1}\)
co daje mi wzór :
\(\displaystyle{ a_{n+1}=b \cdot a + c}\)
i wyliczam:
\(\displaystyle{ a_{2}=a \cdot b + c \\
a_{3}=a \cdot b ^{2} + bc + c \\
a_{4}=a \cdot b ^{3} + b ^{2} c +bc +c}\)
itd..
Powstaje mi wzór :
\(\displaystyle{ a_{n+1}=ab^{n} + c \cdot ( 1 + b + b^{2} +...+ b^{n-1})}\)

Jednak nie potrafię dojść do wzoru, który uzyskał Qń. Czy tym sposobem dojdę do uzyskania poprawnego wzoru czy konieczne jest użycie funkcji tworzących ?

[Xitami]

... _relations

[abc666]

ktosztlumu,
mamy
\(\displaystyle{ a_{n+1}=2a_n+2n+1}\)
Możemy zrobić podstawienie takie aby czynnik \(\displaystyle{ 2n+1}\) się zredukował.

\(\displaystyle{ a_{n}=b_{n}+Cn+D}\)

gdzie \(\displaystyle{ C}\) i \(\displaystyle{ D}\) są pewnymi stałymi, dostajemy:

\(\displaystyle{ b_{n+1}+C(n+1)+D=2(b_{n}+Cn+D)+2n+1}\)
i po uporządkowaniu
\(\displaystyle{ b_{n+1}=2b_{n}+n(2+C)+D+1-C}\)
Chcemy aby \(\displaystyle{ n(2+C)+D+1-C\equiv 0}\) skąd \(\displaystyle{ C=-2}\) i \(\displaystyle{ D=-3}\)
Dostajemy
\(\displaystyle{ b_{n+1}=2b_{n}}\) skąd oczywiście
\(\displaystyle{ b_{n+1}=2^{n}\cdot b_{1}}\)
i
\(\displaystyle{ b_{n}=2^{n-1}\cdot b_{1}}\)
Teraz wracamy do podstawienia
\(\displaystyle{ a_{n}+2n+3=2^{n-1}\cdot 6\\
a_{n}=3\cdot 2^{n}-2n-3}\)

[ktosztlumu]

Wszystko zrozumiałem prócz tego iż b1 = C*D dlaczego tak ? bo rozumiem, że stąd wzięło się w przedostatnim wzorze *6

[abc666]

Mamy
\(\displaystyle{ a_{n}=b_{n}+Cn+D}\)
skąd
\(\displaystyle{ b_{n}=a_{n}-Cn-D}\)
co dla naszych \(\displaystyle{ C}\) i \(\displaystyle{ D}\) daje
\(\displaystyle{ b_{1}=a_{1}+2\cdot 1+ 3=1+2+3=6}\)

[ktosztlumu]

Czy da się rozwiązać to równanie rekurencyjne drzewem rekursji i czy ktoś mógłby pokazać w jaki sposób można tego dokonać?

[Xitami]

\(\displaystyle{ a_n=n^2 +\sum_{k=1}^{n-1}a_k\\\\\\
b_n=\frac{(2n+1)(n^2+n)}{6}\\\\
c_n=3\cdot2^n-2n-3\\\\
d_n=4d_{n-1}-6d_{n-2}+4d_{n-3}-d_{n-4}\\\\
\begin{tabular}{r|rrrr}
n&a_n & b_n & c_n&d_n \\ \hline
1&1&1&1&1\\
2&5&5&5&5\\
3&14&14&15&14\\
4&30&30&37&30\\
5&55&55&83&55\\
6&91&91&177&91\\
7&140&140&367&140\\
8&204&204&749&204\\
9&285&285&1515&285\\
10&385&385&3049&385
\end{tabular}}\)

[abc666]

Xitami, źle obliczyłeś \(\displaystyle{ a_{n}}\)

\(\displaystyle{ a_{2}=4+\overbrace{1}^{a_{1}}\\
a_{3}=9+\overbrace{1+4}^{a_{2}}+\overbrace{1}^{a_{1}}}\)