Lecture - I

Recussive Relation

1. Substitution Method
2. R. Tree Method
3. Masters Theorem

Substitution Method

$$\begin{array}{rl}{a}_n& =a_{n-1}+f_n\\ n=1:a_1& =a_0+f_1\\ n=2:a_2& =a_1+f_2\\ & =(a_0+f_1)+f_2\\ & =a_0+f_1+f_2\\ n=3:a_3& =a_2+f_3\\ & =(a_0+f_1+f_2)+f_3\\ & =a_0+f_1+f_2+f_3\\ ⋮& \\ a_n& =a_0+\sum _{i=1}^n{f}_i\end{array}$$

Question

$\begin{array}{rl}{a}_n& =a_{n-1}+n^2,a_0=7\end{array}$

$$\begin{array}{rl}{a}_n& =a_{n-1}+n^2,a_0=7\\ n=1:a_1& =a_0+1^2\\ & =7+1\\ n=2:a_2& =a_1+2^2\\ & =(7+1)+4\\ & =7+1+4\\ n=3:a_3& =a_2+3^2\\ & =(7+1+4)+9\\ & =7+1+4+9\\ ⋮& \\ a_n& =7+\sum _{i=1}^n{i}^2\\ & =7+\frac{n(n+1)(2n+1)}{6}\end{array}$$

Question

$\begin{array}{rl}{a}_n& =a_{n-1}+\frac{1}{n(n+1)},a_0=1\end{array}$

$$\begin{array}{rl}{a}_n& =a_{n-1}+\frac{1}{n(n+1)},a_0=1\\ n=1:a_1& =a_0+\frac{1}{1\cdot 2}\\ & =1+\frac{1}{2}\\ n=2:a_2& =a_1+\frac{1}{2\cdot 3}\\ & =\left(1+\frac{1}{2}\right)+\frac{1}{6}\\ & =1+\frac{1}{2}+\frac{1}{6}\\ n=3:a_3& =a_2+\frac{1}{3\cdot 4}\\ & =\left(1+\frac{1}{2}+\frac{1}{6}\right)+\frac{1}{12}\\ & =1+\frac{1}{2}+\frac{1}{6}+\frac{1}{12}\\ ⋮& \\ a_n& =1+\sum _{i=1}^n\frac{1}{i(i+1)}\\ & =1+\sum _{i=1}^n\left(\frac{1}{i}-\frac{1}{i+1}\right)\\ & =1+\left(1-\frac{1}{n+1}\right)\\ & =2-\frac{1}{n+1}\end{array}$$

Intermediate

$$\begin{array}{rl}& \left(1-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{3}\right)+\left(\frac{1}{3}-\frac{1}{4}\right)+\cdots +\left(\frac{1}{n}-\frac{1}{n+1}\right).\end{array}$$

Now notice that everything cancels:

$$\begin{array}{rl}1& -\cancel{\frac{1}{2}}+\cancel{\frac{1}{2}}-\cancel{\frac{1}{3}}+\cancel{\frac{1}{3}}-\cancel{\frac{1}{4}}+\cdots +\cancel{\frac{1}{n}}-\frac{1}{n+1}.\end{array}$$

Question

$$\begin{array}{rl}{a}_n& =a_{n-1}+3^n,a_0=1\end{array}$$

$$\begin{array}{rl}{a}_n& =a_{n-1}+3^n,a_0=1\\ n=1:a_1& =a_0+3^1\\ & =1+3\\ n=2:a_2& =a_1+3^2\\ & =(1+3)+9\\ & =1+3+9\\ n=3:a_3& =a_2+3^3\\ & =(1+3+9)+27\\ & =1+3+9+27\\ ⋮& \\ a_n& =1+\sum _{i=1}^n{3}^i\\ & =1+\frac{3(3^n-1)}{3-1}\\ & =1+\frac{3^{n+1}-3}{2}\\ & =\frac{3^{n+1}-1}{2}\end{array}$$

Question

$$\begin{array}{rl}{a}_n& =a_{n-1}+\frac{n(n+1)}{2}\end{array}$$

$$\begin{array}{rl}{a}_n& =a_{n-1}+\frac{n(n+1)}{2}\\ n=1:a_1& =a_0+\frac{1\cdot 2}{2}\\ & =a_0+1\\ n=2:a_2& =a_1+\frac{2\cdot 3}{2}\\ & =(a_0+1)+3\\ & =a_0+1+3\\ n=3:a_3& =a_2+\frac{3\cdot 4}{2}\\ & =(a_0+1+3)+6\\ & =a_0+1+3+6\\ ⋮& \\ a_n& =a_0+\sum _{i=1}^n\frac{i(i+1)}{2}\\ & =a_0+\frac{1}{2}\sum _{i=1}^n(i^2+i)\\ & =a_0+\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right)\\ & =a_0+\frac{n(n+1)(n+2)}{6}\end{array}$$

Important

Find Complexity for

i. Palindrome of a String

$$f_{n+1}=f_{n-1}+f_n$$