Algebra Theory - Recurrence Relations - 2

Now, let's shift our focus to first-order non-linear recurrence relations.

1. First-order non-linear recurrence relation - Type 1.


an=αan−1βan−1+γa_n = \frac{\alpha a_{n-1}}{\beta a_{n-1} + \gamma} βanan−1+γan=αan−1\beta a_n a_{n-1} + \gamma a_n = \alpha a_{n-1} 1an=βan−1+γαan−1\frac{1}{a_n} = \frac{\beta a_{n-1} + \gamma}{\alpha a_{n-1}} 1an=βα+γαan−1\frac{1}{a_n} = \frac{\beta}{\alpha} + \frac{\gamma}{\alpha a_{n-1}} 1an=bn;bn=C2+C1bn−1\frac{1}{a_n} = b_n \quad ; \quad b_n = C_2 + C_1 b_{n-1}

→ So after this transformation we have got first order linear non-homogeneous constant coefficient recurrence relation which we had solved earlier 

Example 1:


an=(n−2)an−1(n−1)−an−1for all n≥3,a1=1,a2=14a_n = \frac{(n - 2) a_{n-1}}{(n - 1) - a_{n-1}} \quad \text{for all } n \geq 3, \quad a_1 = 1, \quad a_2 = \frac{1}{4} 1an=(n−1)−an−1(n−2)an−1=n−1(n−2)an−1−an−1(n−2)an−1\frac{1}{a_n} = \frac{(n - 1) - a_{n-1}}{(n - 2) a_{n-1}} = \frac{n - 1}{(n - 2) a_{n-1}} - \frac{a_{n-1}}{(n - 2) a_{n-1}} 1an=n−1(n−2)an−1−1n−2\frac{1}{a_n} = \frac{n - 1}{(n - 2) a_{n-1}} - \frac{1}{n - 2} 1(n−1)an=1(n−2)an−1−1(n−1)(n−2)\frac{1}{(n - 1) a_n} = \frac{1}{(n - 2) a_{n-1}} - \frac{1}{(n - 1)(n - 2)}

1(n−1)an=bn;bn=bn−1−1(n−1)(n−2)\frac{1}{(n - 1) a_n} = b_n \quad ; \quad b_n = b_{n-1} - \frac{1}{(n - 1)(n - 2)} bn−bn−1=−1(n−1)(n−2)b_n - b_{n-1} = -\frac{1}{(n - 1)(n - 2)} =−((n−1)−(n−2)(n−1)(n−2))= - \left( \frac{(n - 1) - (n - 2)}{(n - 1)(n - 2)} \right) =−(1n−2−1n−1)= - \left( \frac{1}{n - 2} - \frac{1}{n - 1} \right) bn−bn−1=1n−1−1n−2b_n - b_{n-1} = \frac{1}{n - 1} - \frac{1}{n - 2}

b3−b2=12−11b_3 - b_2 = \frac{1}{2} - \frac{1}{1} b4−b3=13−12b_4 - b_3 = \frac{1}{3} - \frac{1}{2} ⋮\vdots bn−bn−1=1n−1−1n−2b_n - b_{n-1} = \frac{1}{n - 1} - \frac{1}{n - 2}

bn−b2=1n−1−1‾\underline{b_n - b_2 = \frac{1}{n - 1} - 1}

1(n−1)an−1(2−1)a2=1n−1−1\frac{1}{(n - 1) a_n} - \frac{1}{(2 - 1) a_2} = \frac{1}{n - 1} - 1 1(n−1)an−114=1n−1−1\frac{1}{(n - 1) a_n} - \frac{1}{\frac{1}{4}} = \frac{1}{n - 1} - 1 1(n−1)an−4=1n−1−1\frac{1}{(n - 1) a_n} - 4 = \frac{1}{n - 1} - 1

1(n−1)an−4=1n−1−1\frac{1}{(n - 1)a_n} - 4 = \frac{1}{n - 1} - 1 1(n−1)an=1n−1+3\frac{1}{(n - 1)a_n} = \frac{1}{n - 1} + 3 1an=1+3(n−1)\frac{1}{a_n} = 1 + 3(n - 1) 1an=1+3n−3\frac{1}{a_n} = 1 + 3n - 3 an=13n−2a_n = \frac{1}{3n - 2}

1. First-order non-linear recurrence relation - Type 2.

an=αan−1+βγan−1+δa_n = \frac{\alpha a_{n-1} + \beta}{\gamma a_{n-1} + \delta}

an=bn+λa_n = b_n + \lambda bn+λ=α(bn−1+λ)+βγ(bn−1+λ)+δb_n + \lambda = \frac{\alpha (b_{n-1} + \lambda) + \beta}{\gamma (b_{n-1} + \lambda) + \delta} bn=α(bn−1+λ)+βγ(bn−1+λ)+δ−λb_n = \frac{\alpha (b_{n-1} + \lambda) + \beta}{\gamma (b_{n-1} + \lambda) + \delta} - \lambda bn=αbn−1+αλ+β−λγbn−1−λ2γ−δλγ(bn−1+λ)+δb_n = \frac{\alpha b_{n-1} + \alpha \lambda + \beta - \lambda \gamma b_{n-1} - \lambda^2 \gamma - \delta \lambda}{\gamma (b_{n-1} + \lambda) + \delta} =(α−λγ)bn−1+(αλ+β−λ2γ−δλ)γ(bn−1+λ)+δ= \frac{(\alpha - \lambda \gamma) b_{n-1} + (\alpha \lambda + \beta - \lambda^2 \gamma - \delta \lambda)}{\gamma (b_{n-1} + \lambda) + \delta}

To simplify this to a linear form, the numerator must cancel out the γ(bn−1+λ)+δ\gamma (b_{n-1} + \lambda) + \delta in the denominator.

So, set:

αλ+β−λ2γ−δλ=0\alpha \lambda + \beta - \lambda^2 \gamma - \delta \lambda = 0

Which leads to:

γλ2+δλ−αλ−β=0\gamma \lambda^2 + \delta \lambda - \alpha \lambda - \beta = 0

Or,

γλ2+(δ−α)λ−β=0\gamma \lambda^2 + (\delta - \alpha) \lambda - \beta = 0

Example 2:


Given:

a1=1,an+1an=4(an+1−1)Find ana_1 = 1, \quad a_{n+1} a_n = 4(a_{n+1} - 1) \quad \text{Find } a_n

Step-by-step:

an+1an=4an+1−4a_{n+1} a_n = 4 a_{n+1} - 4 an+1an−4an+1=−4a_{n+1} a_n - 4 a_{n+1} = -4 an+1(an−4)=−4a_{n+1}(a_n - 4) = -4 an+1=−4an−4⇒an+1=44−ana_{n+1} = \frac{-4}{a_n - 4} \quad \Rightarrow \quad a_{n+1} = \frac{4}{4 - a_n}

Compare to:

an+1=αan+βγan+δ⇒α=0, β=4, γ=−1, δ=4a_{n+1} = \frac{\alpha a_n + \beta}{\gamma a_n + \delta} \quad \Rightarrow \quad \alpha = 0,\ \beta = 4,\ \gamma = -1,\ \delta = 4

Substitution:

Assume:

an=bn+λa_n = b_n + \lambda bn+1+λ=44−(bn+λ)b_{n+1} + \lambda = \frac{4}{4 - (b_n + \lambda)} bn+1=44−bn−λ−λb_{n+1} = \frac{4}{4 - b_n - \lambda} - \lambda bn+1=4−4λ+λbn+λ24−bn−λb_{n+1} = \frac{4 - 4\lambda + \lambda b_n + \lambda^2}{4 - b_n - \lambda}

bn+1=λbn+λ2−4λ+44−bn−λb_{n+1} = \frac{\lambda b_n + \lambda^2 - 4\lambda + 4}{4 - b_n - \lambda} λ2−4λ+4=0\lambda^2 - 4\lambda + 4 = 0 (λ−2)2=0⇒λ=2(\lambda - 2)^2 = 0 \Rightarrow \lambda = 2

Substitute λ=2\lambda = 2:

bn+1=2bn4−bn−2=2bn2−bnb_{n+1} = \frac{2 b_n}{4 - b_n - 2} = \frac{2 b_n}{2 - b_n}

Now simplify:

1bn+1=2−bn2bn\frac{1}{b_{n+1}} = \frac{2 - b_n}{2 b_n} 1bn+1=1bn−12\frac{1}{b_{n+1}} = \frac{1}{b_n} - \frac{1}{2}

1bn+1=Cn+1\frac{1}{b_{n+1}} = C_{n+1} Cn+1=Cn−12C_{n+1} = C_n - \frac{1}{2} Cn+1−Cn=−12⇒Cn is an AP of common difference −12C_{n+1} - C_n = -\frac{1}{2} \quad \Rightarrow \quad C_n \text{ is an AP of common difference } -\frac{1}{2} Cn=C1+(n−1)(−12)C_n = C_1 + (n-1)(-\frac{1}{2})

1bn=1b1−n−12\frac{1}{b_n} = \frac{1}{b_1} - \frac{n - 1}{2} 1an−2=1a1−2−n−12\frac{1}{a_n - 2} = \frac{1}{a_1 - 2} - \frac{n - 1}{2}

Given:

a1=1⇒1a1−2=11−2=−1a_1 = 1 \Rightarrow \frac{1}{a_1 - 2} = \frac{1}{1 - 2} = -1 1an−2=−1−n−12\frac{1}{a_n - 2} = -1 - \frac{n - 1}{2} 1an−2=−2−(n−1)2=−1−n2\frac{1}{a_n - 2} = \frac{-2 - (n - 1)}{2} = \frac{-1 - n}{2}


an=2nn+1


Now, let's move on to linear homogeneous equation of order 2 with constant coefficients.


an=αan−1+βan−2(Assume solution of the form an=xn)a_n = \alpha a_{n-1} + \beta a_{n-2} \quad \text{(Assume solution of the form } a_n = x^n\text{)}

Substituting:

an=xn,an−1=xn−1,an−2=xn−2a_n = x^n, \quad a_{n-1} = x^{n-1}, \quad a_{n-2} = x^{n-2} xn=αxn−1+βxn−2x^n = \alpha x^{n-1} + \beta x^{n-2}

Divide both sides by xn−2x^{n-2}:

x2=αx+β⇒x2−αx−β=0x^2 = \alpha x + \beta \Rightarrow x^2 - \alpha x - \beta = 0

This is a characteristic equation, with roots k1k_1 and k2k_2.

Case 1: k1≠k2k_1 \ne k_2

an=λ(k1)n+μ(k2)na_n = \lambda (k_1)^n + \mu (k_2)^n

Case 2: k1=k2k_1 = k_2

an=(λ+μn)(k1)na_n = (\lambda + \mu n)(k_1)^n

Example 3:


Given:

an=an−1+2an−2,a1=1,a2=3a_n = a_{n-1} + 2a_{n-2}, \quad a_1 = 1, \quad a_2 = 3

Step 1: Characteristic Equation

x2=x+2⇒x2−x−2=0⇒(x+1)(x−2)=0x^2 = x + 2 \Rightarrow x^2 - x - 2 = 0 \Rightarrow (x + 1)(x - 2) = 0

Roots:

x=−1,x=2x = -1, \quad x = 2

Step 2: General Solution

an=λ(−1)n+μ(2)na_n = \lambda(-1)^n + \mu(2)^n

Step 3: Use Initial Conditions

For n=1n = 1:

a1=λ(−1)1+μ(2)1=−λ+2μ=1(Equation ①)a_1 = \lambda(-1)^1 + \mu(2)^1 = -\lambda + 2\mu = 1 \quad \text{(Equation ①)}

For n=2n = 2:

a2=λ(−1)2+μ(2)2=λ+4μ=3(Equation ②)a_2 = \lambda(-1)^2 + \mu(2)^2 = \lambda + 4\mu = 3 \quad \text{(Equation ②)}

Step 4: Solve the System

From Equation ①:

1=−λ+2μ⇒λ=2μ−11 = -\lambda + 2\mu \Rightarrow \lambda = 2\mu - 1

Substitute into Equation ②:

(2μ−1)+4μ=3⇒6μ−1=3⇒μ=23(2\mu - 1) + 4\mu = 3 \Rightarrow 6\mu - 1 = 3 \Rightarrow \mu = \frac{2}{3}

Then:

λ=3−4μ=3−83=13\lambda = 3 - 4\mu = 3 - \frac{8}{3} = \frac{1}{3}

Final Answer:

an=13(−1)n+23(2)n\boxed{a_n = \frac{1}{3}(-1)^n + \frac{2}{3}(2)^n}


an=2⋅2n+(−1)n3a_n = \frac{2 \cdot 2^n + (-1)^n}{3}

Example 4: Fibonacci series


Given recurrence:

an+2=an+1+an,a1=1, a2=1a_{n+2} = a_{n+1} + a_n, \quad a_1 = 1,\ a_2 = 1

Step 1: Characteristic Equation

x2=x+1⇒x2−x−1=0x^2 = x + 1 \Rightarrow x^2 - x - 1 = 0 x=1±1+42=1±52x = \frac{1 \pm \sqrt{1 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2}

Step 2: General Solution

an=λ(1+52)n+μ(1−52)na_n = \lambda \left(\frac{1 + \sqrt{5}}{2}\right)^n + \mu \left(\frac{1 - \sqrt{5}}{2}\right)^n

Step 3: Apply Initial Conditions

For n=1n = 1:

1=λ(1+52)+μ(1−52)(Equation ①)1 = \lambda \left(\frac{1 + \sqrt{5}}{2}\right) + \mu \left(\frac{1 - \sqrt{5}}{2}\right) \quad \text{(Equation ①)}

For n=2n = 2:

1=λ(1+52)2+μ(1−52)21 = \lambda \left(\frac{1 + \sqrt{5}}{2}\right)^2 + \mu \left(\frac{1 - \sqrt{5}}{2}\right)^2 1=λ(3+52)+μ(3−52)(Equation ②)1 = \lambda \left(\frac{3 + \sqrt{5}}{2}\right) + \mu \left(\frac{3 - \sqrt{5}}{2}\right) \quad \text{(Equation ②)}

Step 4: Solve the System

Subtracting (①) from (②):

0=λ(3+52−1+52)+μ(3−52−1−52)0 = \lambda \left( \frac{3 + \sqrt{5}}{2} - \frac{1 + \sqrt{5}}{2} \right) + \mu \left( \frac{3 - \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2} \right) 0=λ(1)+μ(1)⇒λ+μ=00 = \lambda(1) + \mu(1) \Rightarrow \boxed{\lambda + \mu = 0}

Example 5:


an=−4an−1−7an−2,a0=1,a1=−4a_n = -4a_{n-1} - 7a_{n-2}, \quad a_0 = 1, \quad a_1 = -4

Find no. of positive integral divisors of (a50)2−a49a51

Solution:
Let:

bn=(an)2−an−1an+1b_n = (a_n)^2 - a_{n-1} a_{n+1}

Given:

an+1=−4an−7an−1a_{n+1} = -4a_n - 7a_{n-1}

Substitute:

bn=an2−an−1(−4an−7an−1)b_n = a_n^2 - a_{n-1}(-4a_n - 7a_{n-1}) =an2+4anan−1+7an−12= a_n^2 + 4a_n a_{n-1} + 7a_{n-1}^2 =an(an+4an−1)+7an−12= a_n(a_n + 4a_{n-1}) + 7a_{n-1}^2

Now use:

an=−4an−1−7an−2⇒an+4an−1=−7an−2a_n = -4a_{n-1} - 7a_{n-2} \Rightarrow a_n + 4a_{n-1} = -7a_{n-2}

So:

bn=an(−7an−2)+7an−12=−7anan−2+7an−12b_n = a_n(-7a_{n-2}) + 7a_{n-1}^2 = -7a_n a_{n-2} + 7a_{n-1}^2 bn=7(an−12−anan−2)b_n = 7(a_{n-1}^2 - a_n a_{n-2})

Thus, we have the recurrence:

bn=7bn−1\boxed{b_n = 7b_{n-1}}

We have the recurrence:

bn=7bn−1⇒Geometric progressionb_n = 7b_{n-1} \Rightarrow \text{Geometric progression}

So:

bn=b1⋅7n−1b_n = b_1 \cdot 7^{n-1}

Step: Compute b1b_1

Given:

a0=1,a1=−4a_0 = 1, \quad a_1 = -4

Use recurrence to compute:

a2=−4a1−7a0=−4(−4)−7(1)=16−7=9a_2 = -4a_1 - 7a_0 = -4(-4) - 7(1) = 16 - 7 = 9

Then:

b1=a12−a0a2=(−4)2−1⋅9=16−9=7b_1 = a_1^2 - a_0 a_2 = (-4)^2 - 1 \cdot 9 = 16 - 9 = 7

Therefore:

bn=7n⇒b50=750b_n = 7^n \quad \Rightarrow \quad b_{50} = 7^{50}

Final Step: Number of positive integral divisors of b50=750b_{50} = 7^{50}

Since 7507^{50} is a power of a prime:

Number of positive divisors=50+1=51\text{Number of positive divisors} = 50 + 1 = \boxed{51}


Comments

Post a Comment

Popular posts from this blog

IOQM 2024 Paper solutions (Done 1-21, 29)

Image
Q1 (number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is: Solution : This product has all the integers from 1 to 9. So smallest integer not dividing it would be the next prime after 9. Which is 11. Answer: 11 Q2 (combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is: Solution: Last digit has to be 1 or 3: 2C1 Choosing remaining 3 digits: 3C3 Arranging those 3 digits: 3! Answer: 2C1*3C3*3! = 12 Q3 (number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is: Solution: To get last 2 digits from number, divide by 100 and take the remainder. So we have to compute mod 100. 25 mod 100 = 25 25.5 mod 100 = 125 mod 100 = 25 5^3.5 mod 100 = 25.5 mod 100 = 25 5^4.5 mod 100 = 25.5 mod 100 = 25 ..... So: 5^2024 mod 100 = 25. Q4 (geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\...
Read more

Combinatorics DPP - RACE 6 - Q16 pending discussion

Image
Q1 . A question paper consists of two sections. Section A has 7 questions and section B has 8 questions. A student has to answer 10 questions out of these 15 questions. The number of ways in which he can answer if he must answer at least 3 of section A and at least 4 of the section B is: Solution: One wrong way to solve this: For the mandatory questions: 7C3*8C4 Now 3 more questions need to be answered from 4 of A and 4 of B. Cases: 3A,0B | 2A,1B | 1A,2B | 0A,3B 4C3*4C0 + 4C2*4C1 + 4C1*4C2 + 4C0*4C1 = 4 + 24 + 24 + 4 = 56 Finally: 7C3*8C4*56 = 35*70*56 = 137200 Why is it wrong? Let's say we chose A1,A2,A3 as mandatory from A and then chose A4,A5,A6 when we did 4C3*4C0 for (3A,0B). But we could have done it the other way round also, i.e. choose A4,A5,A6 as mandatory and then choose A1,A2,A3. So there is overcounting. Correct Solution : Simply create the cases for A,B: (3,7),(4,6),(5,5),(6,4) 7C3*8C7 + 7C4*8C6 + 7C5*8C5 + 7C6*8C4 = 2926. Q2 . A kindergarten teacher has 25 kids in her...
Read more

Algebra DPP 1.3 Quadratics

 Q1 . For what values of b do the equations: 1988x² + bx + 8891 = 0 and 8891x² + bx + 1988 = 0 have a common root? Solution: We are given two quadratic equations: 1988 x 2 + b x + 8891 = 0 1988x^2 + bx + 8891 = 0 8891 x 2 + b x + 1988 = 0 8891x^2 + bx + 1988 = 0 We are to find the values of b b for which they have a common root . Step 1: Let α \alpha be the common root. Then α \alpha satisfies both equations. So, From equation (1): 1988 α 2 + b α + 8891 = 0 (i) 1988\alpha^2 + b\alpha + 8891 = 0 \quad \text{(i)} From equation (2): 8891 α 2 + b α + 1988 = 0 (ii) 8891\alpha^2 + b\alpha + 1988 = 0 \quad \text{(ii)} Step 2: Subtract equation (i) from equation (ii): ( 8891 α 2 − 1988 α 2 ) + ( b α − b α ) + ( 1988 − 8891 ) = 0 (8891\alpha^2 - 1988\alpha^2) + (b\alpha - b\alpha) + (1988 - 8891) = 0 ( 8891 − 1988 ) α 2 − ( 8891 − 1988 ) = 0 (8891 - 1988)\alpha^2 - (8891 - 1988) = 0 6903 α 2 − 6903 = 0 6903\alpha^2 - 6903 = 0 α 2 = 1 ⇒ α = ± 1 \alpha^2 = 1 \Rightar...
Read more