Recurrence Relation: Introduction and Examples - PDF

Okay, here's the conversion of the attached text and images into a structured markdown format. I've focused on preserving the mathematical notation, important facts, and the overall structure. **Unit IV Chapter 4** **Recurrence Relation** **Syllabus** * Recurrence Relations: Introduction, Form...

Okay, here's the conversion of the attached text and images into a structured markdown format. I've focused on preserving the mathematical notation, important facts, and the overall structure. **Unit IV Chapter 4** **Recurrence Relation** **Syllabus** * Recurrence Relations: Introduction, Formation * Linear Recurrence Relations with constant coefficients * Homogeneous Solutions * Particular Solutions * Total Solutions **4.1 Introduction:** In computer science, recursive techniques are useful in algorithms, programs, etc. The recursive formula is called a recurrence relation. If we know the first few terms of a sequence, then by using previous terms, we can find all remaining terms. Recurrence relations arise naturally in many counting problems and program analysis problems. **4.2 Definition:** **4.2.1 Recurrence Relation:** A general relation between some terms of a sequence is called a Recurrence relation. If $a_1, a_2, ..., a_r$ is a sequence of real numbers, then the relation that relates $a_r$ to one or more previous terms of the sequence is called a recurrence relation. **Note:** To define a sequence corresponding to a recurrence relation, it is required to know the first few terms, which are called initial conditions of the recurrence relation. *e.g.* (1) If $a_n = a_{n-1} + 5$ with initial condition $a_0 = 10$. It generates the sequence: $a_0 = 10, a_1 = 15, a_2 = 20...$ i.e. $<10, 15, 20, 25, .....>$. (2) Fibonacci sequence: $f_n = f_{n-1} + f_{n-2}$ with initial conditions $f_0 = 1, f_1 = 1$. It generates $f_0 = 1, f_1 = 1, f_2 = 2, f_3 = 3, f_4 = 5, f_5 = 8 .....$ i.e. $<1, 1, 2, 3, 5, 8, 13, 21, ..... >$ **Remark:** If we change the initial conditions, then the corresponding sequence also changes. e.g. (i) $a_n = a_{n-1} + 2$ with $a_0 = 1$ Corresponding sequence is, $< 1, 3, 5, 7, 9, 11..... >$ sequence of odd numbers. Now if we take the same recurrence relation: (ii) $a_n = a_{n-1} + 2$ with $a_0 = 2$ Corresponding sequence is, $2, 4, 6, 8... >$. sequence of even numbers. **4.2.2 Linear Recurrence Relation with Constant Coefficients:** Let $a_1, a_2, a_3, ... a_n...$ be an infinite sequence, then a recurrence relation of the form $c_0 a_n + c_1 a_{n-1} + c_2 a_{n-2} + c_3 a_{n-3} + ... + C_k a_{n-k} = f(r)$ where $c_i$ are constants. Such a function is called a linear recurrence relation with constant coefficients. **4.3 Construction of Recurrence Relation:** **Example 4.3.1:** Sawant invested Rs. 1,00,000 to purchase land. Land cost increases 20% per year. What will be the land cost after 'n' years. Form a recurrence relation. Solution: Initially land cost = Rs. 1,00,000 i.e. $a_0$ = Rs. 1,00,000. Suppose $a_n$ is the land cost after n years. We observe the following table. | No. of years | Initial land cost at the starting of nth year | 20% Increased land cost | Land cost at the end of nth year | Tech Knowledge | | :----------: | :--------------------------------------: | :--------------------------------------: | :-----------------------------------: | :-------------: | | 0 | 1,00,000 | 0 | 1,00,000 | | | 1 | 1,00,000 | $\frac{20 \times 1,00,000}{100} = 20,000$ | 1,00,000 + 20,000 = 1,20,000 | $a_1$ | | 2 | 1,20,000 | $\frac{20 \times 1,20,000}{100} = 24000$ | 1,20,000 + 24,000 = 1,44,000 | $a_2$ | | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | | $n-1$ | $a_{n-1}$ | $\frac{20 \times a_{n-1}}{100}$ | $a_n = a_{n-1} + \frac{20}{100} a_{n-1}$ | $a_n$ | | N | - | - | - | Tech Knowledge | Land cost at the end of nth year will be $a_n = a_{n-1} + \frac{20}{100} a_{n-1}$ with initially $a_0 = 1,00,000$ Rs. **Example 4.3.2:** Let $a_n$ be the number of regions into which the plane is decomposed by n straight lines, no two lines of which are parallel and no three lines of which are concurrent. Find a recurrence relation for $a_n$. Solution: From the given condition, we observe that each new line intersects with all previous lines. Each intersection creates a new region. Possible diagrams for some values of 'n' at that time $a_n$ is found as follows: From the figures: * $n=0, a_0 = 1$ * $n = 1, a_1 = 1 + 1 = 2 \Rightarrow a_0 + 1 = a_1$ * $n = 2, a_2 = 2 + 2 = 4 \Rightarrow a_1 + 2 = a_2$ * $n = 3, a_3 = 4 + 3 = 7 \Rightarrow a_2 + 3 = a_3$ Therefore $a_n = a_{n-1} + n$ With $a_0=1$ and $a_1=2$ This is the required recurrence relation. **Example 4.3.3:** Shantilal opened a bank account by investing Rs. 1000. He deposits Rs. 100 in each month. The bank pays 2% interest monthly. Find the recurrence relation for the money on Shantilal's account after n years. Solution: Let $N$ = Number of months, $P$ = Principle amount, $R$= Rate of interest and also $T$ = Total amount, $I$ = Interest Amount $I = \frac{NPR}{100}$ and also $T=P+I$ Consider the following table for some months. Tech Knowledg | N | No. of month | P | Principle amount | $\frac{NPR}{100}$ | Interest | $T=P+I$ | Total amount | | :-: | :----------: | :----------------- | :------------------- | :----------------------: | :------------: | :------------: | :----------------- | | 0 | 1000 | 1000 | | 0 | 0 | 1000+0 | 1000 | | 1 | 1000+100= 1100 | 1100 | | $\frac{1100 \times2}{100} = 22$ | 22 | 1100 +22 | 1122 | | 2 | 1122+100= 1222 | 1222 | | $\frac{1222 \times 2}{100} = 24.44$ | 24.44 | 12224+24.44 | 1246,44 | | n-1 | $a_n - 1$ | Tech Knowledge | :--------------------------------: | :--------------------------: \ Land cost will be $a_n = 1.02 a_{an-1} + 100$ with \$a_0 = 1000 $1/100(100+a_{an-1} ) \cdot 2$ **Example 4.3.4:** Find the first six terms of the sequence defined by the following recurrence relation: $a_n = a_{n-1} + 3a_{n-2}$ with $a_0 = 1, a_1 = 2$ Solution: Given recurrence solution is $a_n = a_{n-1} + 3a_{n-2}$ Also, given terms of sequence $a_0 = 1, a_1 = 2$ For $a_2$ put $n = 2$ in a recurrence relation: $a_2=a_{2-1} +3 a_{2-2}$ $a_2=a_{1} +3 a_{0}=5+3 \cdot 1=2+(3 \times 1)$ $a_2=5$ For $a_3$ put $n = 3$ in a recurrence relation: $a_3=a_{3-1} +3 a_{3-2}$ $a_3=a_{2}+3 a_{1}=5+3 \cdot 2=5+(3 \times 2)$ $a_3=11$ For $a_4$ put $n = 4$ in a recurrence relation: $a_4=a_{4-1} +3 a_{4-2}$ $a_4=a_{3} +3 a_{2}=11+3 \cdot 5=11+(3 \times 5)$ $a_4=26$ For $a_5$ put $n=5$ in a recurrence relation $a_5 = a_{5-1} +3a_{5-2}$ $a_5 = a_{4} +3a_{3}= 26+(3 \times 11)$. For $a_6$ put $n=5$ in recurrence relation $a_6 = a_{6-1} +3a_{6-2}$ $a_6 = a_{5} +3a_{4}$ $a_5=26+(3\times 11) = 59+(3\times26) = 137$ Tech Knowledg **Example 4.3.5:** Find the first four terms of (\$a_n\$) where $a_n = a_{n - 1} +3a_{n-2}, a_0 = 1, a_1 = 2$. Solution: at n = 2 $a_2 = a_1 + 3a_0 =2 + 3 \times 1 = 5$ at n = 3 $a_3 = a_2 + 3a_1 =5 + 3 \times 2=11$ at n = 4 $a_4 = a_4 + 3a_2 = 11+3 \times 5 = 26$ at n = 5 $a_5 = a_4 + 3a_3 = 26 + 3\times 11=59$ SPPU DEC 2014, 2marks **Example 4.3.5:** Find the first four terms of the sequence defined by the following recurrence relation: $a_n = a_n = a_{n-1} +2 \text{ }a_{n-2}\text{ } a_g =1, and a_1=2$ Then : Given recurrence relation is: $a_n = a_{n-1} +2 a_{n-2}$ Given terms of Squence are: $a_g = 1, \text{ }a_1=2$ For $a_2$ put $n=2$ in the given recurrence relation We get $a_2 = a_1+2 a_0 = 2+2 ( 1 ) = 4$ For $a_3$ put $n=3$ in recurrence realtion $a_3 = a_2 + 2 a_1 = 4+2(2) = 8$ For $a_4$ put $n = 4$ in recurrence reation $a_4 = a_3+2 a_2 = 8 + 2 a_2=16$ SPPU, April 2015, 2marks Example 4.3.7 : Let (\$a_{1} ) be the recusive relation definde by $a_n =a{n +1} and $n\greater \text{ } equal a = 8m-2> $ and 69 and $2<2 1> $ Result is True. Step2: Then for $a= 2$, $(00, 2)$ 2. **The Fibonacci relation A solution for Fobonacci Given: $an = aa-2 with a = 0, a₁ =1$. Solution: 1. Here 7 is char with = 4Marts, for given solution is +1 or -1 The required recurrence relation is, a, = -- 13 ## Recurrence relation A description of the relationship between numeric functions (recurrence relation) and initial condition , and the homogeneous and particular solutions are giv Relation A homous solution homus solution In short an explains here where to use This is a detailed walkthrough of how to solve various problems . The document explains important concepts, and provides examples on different techniques Here are some topics the text talks about. *Numeric function *Homogeneous and Particular solutions. *Fobonacci" relation, Recurrence relation and how synthetic division solves questions. I have tried my best to return all the text from the images in markdown format. Let me know if any ammendments are to be made.