# Find nth term of a given recurrence relation

Let **a _{n}** be a sequence of numbers, which is defined by the recurrence relation

**a**and

_{1}=1**a**. The task is to find the value of

_{n+1}/a_{n}=2^{n}**log**for a given

_{2}(a_{n})**n**.

**Examples:**

Input:5Output:10Explanation:log_{2}(a_{n}) = (n * (n - 1)) / 2 = (5*(5-1))/2 = 10Input:100Output:4950

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

, We multiply all of the above in order to reach

Since . Then

.

Substituting n+1 for n:

So,

Below is the implementation of above approach.

## 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)**