Find nth term of a given recurrence relation
Let an be a sequence of numbers, which is defined by the recurrence relation a1=1 and an+1/an=2n. The task is to find the value of log2(an) for a given n.
Examples:
Input: 5 Output: 10 Explanation: log2(an) = (n * (n - 1)) / 2 = (5*(5-1))/2 = 10
Input: 100 Output: 4950
,
We multiply all of the above in order to reach
Since .
Then,
Substituting n+1 for n:
So, log_{2}(a_{n})=\frac{n(n-1)}{2}
Below is the implementation of the above approach as follows:
C++
// C++ program to find nth term of // a given recurrence relation #include <bits/stdc++.h> using namespace std; // function to return required value int sum( int n) { // Get the answer int ans = (n * (n - 1)) / 2; // Return the answer return ans; } // Driver program int main() { // Get the value of n int n = 5; // function call to print result cout << sum(n); return 0; } |
Java
// Java program to find nth term // of a given recurrence relation import java.util.*; class solution { static int sum( int n) { // Get the answer int ans = (n * (n - 1 )) / 2 ; // Return the answer return ans; } // Driver code public static void main(String arr[]) { // Get the value of n int n = 5 ; // function call to print result System.out.println(sum(n)); } } //This code is contributed byte //Surendra_Gangwar |
Python3
# Python3 program to find nth # term of a given recurrence # relation # function to return # required value def sum (n): # Get the answer ans = (n * (n - 1 )) / 2 ; # Return the answer return ans # Driver Code # Get the value of n n = 5 # function call to prresult print ( int ( sum (n))) # This code is contributed by Raj |
C#
// C# program to find nth term // of a given recurrence relation using System; class GFG { static int sum( int n) { // Get the answer int ans = (n * (n - 1)) / 2; // Return the answer return ans; } // Driver code public static void Main() { // Get the value of n int n = 5; // function call to print result Console.WriteLine(sum(n)); } } // This code is contributed byte // inder_verma |
PHP
<?php // PHP program to find nth term of // a given recurrence relation // function to return required value function sum( $n ) { // Get the answer $ans = ( $n * ( $n - 1)) / 2; // Return the answer return $ans ; } // Driver Code // Get the value of n $n = 5; // function call to print result echo sum( $n ); // This code is contributed by // inder_verma ?> |
Javascript
<script> // Javascript program to find nth term of // a given recurrence relation // function to return required value function sum(n) { // Get the answer let ans = parseInt((n * (n - 1)) / 2); // Return the answer return ans; } // Driver program // Get the value of n let n = 5; // function call to print result document.write(sum(n)); // This code is contributed by subham348. </script> |
Output:
10
Time Complexity: O(1)
Auxiliary Space: O(1) // Because using constant variables