It is a second order recurrence relation.Ĥ Solving Linear Homogenous Recurrence Relations with Constants Coefficients. Here F 0=0 & F 1=1 are called initial conditions. Which can be represented by the recurrence relation.į 0=0,F 1=1. If the terms of a recurrence relation satisfies a recurrence relation, then the sequence is called a solution of the recurrence relation.įor example ,we consider the famous Fibonacci sequence The degree is k because an is exrressed in terms of the previous k terms of the sequenceĭoes not have constant coefficient Ex:6 The relation T(k)=2 2KT(K-3) Is a third order recurrence relation & T(0),T(1),T(2) are the initial conditions.Įx:7 The recurrence relation for the functionĪn equation that expresses a n, the general term of the sequence or a difference equation. The coefficients of the terms of the sequence are all constants ,ra ther tha fu tio that depe ds o. The recurrence relation is homogeneous, since no terms occur that are ot ultiplies of the aj s. The recurrence relation in the definition is linesr since the right hand side is the sum of multiplies of the previous terms of sequence. Number of ways selecting 4 balls and all Of same colour is = 6C 4 + 5C 4Ī Linear homogeneous recurrence relation of degree K with constant coefficients is a recurrence relation of the form Number of ways selecting 4 balls 2 must be red. The 2 red balls can be chosen in 5C 2 ways. (2) The 2 white balls can be chosen in 6C 2 ways. Sol : (1) 4 balls of any colour can be chosen from 11 balls (6+5) in 11C 4 ways. (d) For the committee of bath sexes we have the following possibilities. (b) For the committee of atleast one women we have the following possibilities By product rule the committee of 3 men and 4 women can be selected in 4 women can be selected from 7 women in 7C 4 ways. (a) 3 men can be selected from 6 men is 6C 3 ways. (2) 4 members which has atleast one women. Inductive Step: Assume that P(j) is positive for all integer j with j r=20-(r+2) - à (1)įrom a commitiee consisting of 6 men and 7 women in how many ways can be select a committee of Let P(n) be the proportion that n can be written as the product of primesīasis Step : P(2) is true, since 2 can be written as the product of one prime The two forms of mathematical induction are equivalent that is, each can be shown to be valid proof technique by assuming the otherĮXAMPLE 1: Show that if n is an integer greater than 1, then n can be written as the product of primes.
We summarize the two steps used to show that p(n)is true for all positive integers n.īasis Step : The proposition P(1) is shown to be true This is called strong Induction (and sometimes also known as the second principles of mathematical induction).
We assume that p(j)is true for j=1 and …,k show that p(k+1)must also be true based on this assumption. There is another form of mathematics induction that is often useful in proofs.In this form we use the basis step as before, but we use a different inductive step. (1) => k 3 – k Is divisible by 3 and 3(k 2 + k) is divisible by 3 ,we have equation (2) is divisible by 3īy the principle of mathematical induction, n 3 - n is divisible by 3. P (k+1) = k (2k-1) (2k+1) +(2k+1) 2 using (1)īY THE PRINCIPLE OF MATHEMATICAL INDUCTION,ĮXAMPLE 6:Use mathematical induction to show that n 3 - n is divisible by 3. Therefore, atleast one hole has more than 1 pigeon. Which is a Þ Ü to our assumption that there are (n+1) pigeon. Since, there are ‘n’ holes, which implies, we have totally ‘n’ pigeon. Therefore, each and every hole has exactly one pigeon. Atleast one hole has not more than one pigeon. If (n=1) pigeon occupies ‘n’ holes then atleast one hole has more than 1 pigeon.Ĭlaim: Atleast one hole has more than one pigeon.