Teraz masz wyrażone T(n) za pomocą T(n-1) i T(1), twoim celem jest wyrazić to samo tylko za pomocą n. Najprostszy sposób to to rozpisać sobie T(n) tak jak poniżej i zgadnąć (zwykle to po prostu widać):
T(n) = T(n-1) + 4(n+1) = |zamieńmy kolejnoć dla wygody|
= 4(n+1) + T(n-1) = | rozpisujemy rekurencyjnie |
= 4(n+1) + 4((n-1) + 1) + T(n-2) =
= 4(n+1) + 4(n) + T(n-2) =
= 4(n+1) + 4(n) + 4((n-2) + 1) + T(n-3) =
= 4(n+1) + 4(n) + 4(n-1) + T(n-3) =
= 4(n+1) + 4(n) + 4(n-1) + 4((n-3)+1) + T(n-4) =
= 4(n+1) + 4(n) + 4(n-1) + 4(n-2) + T(n-4) = |i tak się bawimy jeszcze kilka razy| =
= 4(n+1) + 4(n) + 4(n-1) + 4(n-2) + 4(n-3) + 4(n-4) + 4(n-5) + ... + T(1) =
= 4(n+1) + 4(n) + 4(n-1) + 4(n-2) + 4(n-3) + 4(n-4) + 4(n-5) + ... + 4*3 + 1
teraz jak na to popatrzysz wystarczy zauważyć, że pojawił nam się ciąg arytmetyczny i napisać wzór na sumę ciągu arytmetycznego w tej postaci czyli:
S = (n-1)*(a1 + an)/2 + 1=
= (n-1)*(4*3 + 4(n+1)) / 2 + 1 =
= 6*(n-1) + 2(n-1)(n+1) + 1 =
= 6n - 6 + 2n^2 - 2 + 1 =
= 2n^2 + 6n - 7
Tutaj czeka na ciebie kilka pułapek (żeby nie było zbyt prosto 
):
- ile ten ciąg arytmetyczny ma elementów (u nas jest to (n-1), jeśli tego nie widzisz to po prostu rozpisz sobie T(2), T(3), T(4),
- jaki jest pierwszy element naszego ciągu (u nas jest to 4*3, znowu, jeśli tego nie widzisz ....
- nie zapomnij o tym +1 na końcu, które wzięło się z warunku T(1) = 1 i nie należy do ciągu arytmetycznego (czasem może należeć, czasem nie)
No i w sumie masz wzór:
T(n) = 2n^2 + 6n - 7
Teraz ważna rzecz - rozpisz sobie T(1) T(2) T(3) przy pomocy obu wzorów, w ten sposób łatwo sprawdzisz czy się nie walnąłeś w obliczeniach - WYNIKI MUSZĄ BYĆ TAKIE SAME.
Jak dotąd zgadliśmy wzór T(n), tutaj zwykle będzie się krył ciąg arytmetyczny, geometryczny, lub jakiś inny w zależności jakie znasz, czasem może być ukryty, ale po rozpisaniu próbuj kombinować.
Ale to nie koniec, jesteśmy w połowie drogi, bo jak wielokrotnie podkreślałem wzór na ciąg po prostu zgadliśmy, więc skąd wiemy czy dla T(100) dalej będzie on prawdziwy??? No właśnie, to też trzeba pokazać a do tego służy indukcja i dowodzimy to w 3 krokach:
1. Sprawdzamy T(1):
T(1) = 1
T(1) = 2*1^2 + 6*1 - 7 = 2 + 6 - 7 = 1
zgadza się
2. Założenie indukcyjne - zakładamy, że nasz wzór jest poprawny, więc T(n) = 2n^2 + 6n - 7
3. Teza indukcyjna - pokazujemy, że dla T(n+1) działa (z pierwotnego wzoru)
T(n+1) = T((n + 1) - 1) + 4((n+1) + 1) =
= T(n) + 4(n+2) =
= 2n^2 + 6n - 7 + 4(n+2) =
= 2n^2 + 6n - 7 + 4n + 8 =
= 2n^2 + 10n +1
T(n+1) = 2(n+1)^2 + 6(n+1) - 7 =
= 2n^2 + 4n + 2 + 6n + 6 - 7 =
= 2n^2 + 10n + 1
jak widzisz, po użyciu pierwotnego wzoru i wstawieniu za T(n) nasz wzór (który założyliśmy w 2 punkcie za prawdziwy) wyszło dokładnie to samo, co po podstawieniu (n+1) do naszego wzoru.
I tak się robi takie zadanka, ach się rozpisałem ... ale mam nadzieję ze się choć trochę rozjaśniło.
