A recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given; each further term of the sequence or array is defined as a function of the preceding terms. Below are the steps required to solve a recurrence equation using the polynomial reduction method:
- Form a characteristic equation for the given recurrence equation.
- Solve the characteristic equation and find the roots of the characteristic equation.
- Simplify the solution with unknown coefficients.
- Solve the equation with respect to the initial conditions to get a specific solution.
Example:
Consider the following second-order recurrence equation:
T(n) = a1T(n-1) + a2T(n-2)
For solving this equation formulate it into a characteristic equation.
Let us rearrange the equation as follows:
T(n) - a1T(n-1) - a2T(n-2) = 0
Let, T(n) = xn
Now we can say that T(n-1) = xn-1 and T(n-2)=xn-2
Now the equation will be:
xn + a1xn-1 + a2xn-2 = 0
After dividing the whole equation by xn-2 [since x is not equal to 0] we get:
x2 + a1x + a2 = 0
We have got our characteristic equation as x2+a1x+a2=0
Now, find the roots of this equation.
Three cases may exist while finding the roots of the characteristic equation and those are:
Case 1: Roots of the Characteristic Equation are Real and Distinct
If there are r number of distinct roots for the characteristic equation then it can be said that r number of fundamental solutions are possible. One can take any linear combination of roots to get the general solution of a linear recurrence equation.
If r1, r2, r3……, rk are the roots of the characteristic equation then the general solution of the recurrence equation will be:
tn = c1r1n + c2r2n + c3r3n +...........+ ckrkn
Case 2: Roots of the Characteristic Equation are Real but not Distinct
Let us consider the roots of the characteristic equations are not distinct and the roots r is in the multiplicity of m. In this case, the solution of the characteristic equation will be:
r1 = rn r2 = nrn r3 = n2rn ......... rm = nm-1rn
Therefore, include all the solutions to get a general solution of the given recurrence equation.
Case 3: Roots of the Characteristic Equation are Distinct but Not Real
If the roots of the characteristic equation are complex, then find the conjugate pair of roots.
If r1 and r2 are the two roots of a characteristic equation, and they are in conjugate pair with each other it can be expressed as:
r1 = reix r2 = re-ix
The general solution will be:
tn = rn(c1cos nx + c2sin nx)
Example:
Let’s solve the given recurrence relation:
T(n) = 7*T(n-1) - 12*T(n-2)
Let T(n) = xn
Now we can say that T(n-1) = xn-1 and T(n-2)=xn-2
And dividing the whole equation by xn-2, we get:
x2 - 7*x + 12 = 0
Below is the implementation to solve the given quadratic equation:
C++
// C++ program to find roots// of a quadratic equation#include<bits/stdc++.h>using namespace std;class Quadratic{ public:// Prints roots of quadratic// equation ax * 2 + bx + xvoid findRoots(int a, int b, int c){ // If a is 0, then equation is not // quadratic, but linear if (a == 0) { cout << "Invalid"; return; } int d = b * b - 4 * a * c; float sqrt_val = sqrt(abs(d)); // Real Roots if (d > 0) { cout << "Roots are real and different" << endl; cout << fixed << std::setprecision(1) << float((-b + sqrt_val) / (2 * a)) << endl; cout << fixed << std::setprecision(1) << float((-b - sqrt_val) / (2 * a)) << endl; } // Imaginary Roots else { cout << "Roots are complex" << endl; cout << fixed << std::setprecision(1) << float(b / (2.0 * a)) << " + i" << sqrt_val << endl; cout << fixed << std::setprecision(1) << float(b / (2.0 * a)) << " - i" << sqrt_val << endl; }}};// Driver codeint main(){ Quadratic obj; // Given value of coefficients int a = 1, b = -7, c = 12; obj.findRoots(a, b, c);}// This code is contributed by SURENDRA_GANGWAR |
Java
// Java program to find roots// of a quadratic equationimport java.io.*;import static java.lang.Math.*;class Quadratic { // Prints roots of quadratic // equation ax * 2 + bx + x void findRoots(int a, int b, int c) { // If a is 0, then equation is not // quadratic, but linear if (a == 0) { System.out.println("Invalid"); return; } int d = b * b - 4 * a * c; double sqrt_val = sqrt(abs(d)); // Real Roots if (d > 0) { System.out.println( "Roots are real" + " and different \n"); System.out.println( (double)(-b + sqrt_val) / (2 * a) + "\n" + (double)(-b - sqrt_val) / (2 * a)); } // Imaginary Roots else { System.out.println( "Roots are complex \n"); System.out.println( -(double)b / (2 * a) + " + i" + sqrt_val + "\n" + -(double)b / (2 * a) + " - i" + sqrt_val); } } // Driver code public static void main(String args[]) { Quadratic obj = new Quadratic(); // Given value of coefficients int a = 1, b = -7, c = 12; obj.findRoots(a, b, c); }} |
Python3
# Python3 program to find roots# of a quadratic equationfrom math import sqrt# Prints roots of quadratic# equation ax * 2 + bx + xdef findRoots(a, b, c): # If a is 0, then equation is not # quadratic, but linear if (a == 0): print("Invalid") return d = b * b - 4 * a * c sqrt_val = sqrt(abs(d)) # Real Roots if (d > 0): print("Roots are real and different") print((-b + sqrt_val) / (2 * a)) print((-b - sqrt_val) / (2 * a)) # Imaginary Roots else: print("Roots are complex \n") print(-b / (2 * a), " + i", sqrt_val, "\n", -b / (2 * a), " - i", sqrt_val) # Driver codeif __name__ == '__main__': # Given value of coefficients a = 1 b = -7 c = 12 findRoots(a, b, c)# This code is contributed by mohit kumar 29 |
C#
// C# program to find roots// of a quadratic equationusing System;class Quadratic{// Prints roots of quadratic// equation ax * 2 + bx + xvoid findRoots(int a, int b, int c){ // If a is 0, then equation // is not quadratic, but linear if (a == 0) { Console.WriteLine("Invalid"); return; } int d = b * b - 4 * a * c; double sqrt_val = Math.Sqrt(Math.Abs(d)); // Real Roots if (d > 0) { Console.WriteLine("Roots are real" + " and different \n"); Console.WriteLine((double) (-b + sqrt_val) / (2 * a) + "\n" + (double) (-b - sqrt_val) / (2 * a)); } // Imaginary Roots else { Console.WriteLine("Roots are complex \n"); Console.WriteLine(-(double)b / (2 * a) + " + i" + sqrt_val + "\n" + -(double)b / (2 * a) + " - i" + sqrt_val); }}// Driver codepublic static void Main(String []args){ Quadratic obj = new Quadratic(); // Given value of coefficients int a = 1, b = -7, c = 12; obj.findRoots(a, b, c);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to find roots// of a quadratic equation// Prints roots of quadratic// equation ax * 2 + bx + xfunction findRoots(a, b, c){ // If a is 0, then equation is not // quadratic, but linear if (a == 0) { document.write("Invalid"); return; } let d = b * b - 4 * a * c; let sqrt_val = Math.sqrt(Math.abs(d)); // Real Roots if (d > 0) { document.write( "Roots are real" + " and different <br>"); document.write( (-b + sqrt_val) / (2 * a) + "<br>" + (-b - sqrt_val) / (2 * a)); } // Imaginary Roots else { document.write( "Roots are complex <bR>"); document.write( -b / (2 * a) + " + i" + sqrt_val + "<br>" + -b / (2 * a) + " - i" + sqrt_val); }}// Driver code// Given value of coefficientslet a = 1, b = -7, c = 12;findRoots(a, b, c);// This code is contributed by unknown2108</script> |
Roots are real and different 4.0 3.0
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
