Sum of first n term of Series 3, 5, 9, 17, 33….
Given n, we need to find sum of first n terms of the series represented as Sn = 3 + 5 + 9 + 17 + 33 … upto n
Examples:
Input : 2
Output : 8
3 + 5 = 8
Input : 5
Output : 67
3 + 5 + 9 + 17 + 33 = 67
Let, the nth term be denoted by tn.
This problem can easily be solved by splitting each term as follows :
Sn = 3 + 5 + 9 + 17 + 33……
Sn = (2+1) + (4+1) + (8+1) + (16+1) +……
Sn = (2+1) + (2*2+1) + (2*2*2+1) + (2*2*2*2+1) +……+ ((2*2*2..unto n times) + 1)
We observed that the nth term can be written in terms of powers of 2 and 1.
Hence, the sum of first n terms is given as follows:
Sn = (2+1) + (4+1) + (8+1) + (16+1) +……+ upto n terms
Sn = (1 + 1 + 1 + 1 + …unto n terms) + (2 + 4 + 8 + 16 + …upto nth power of 2)
In above formula,
2 + 4 + 8 + 16…. is a G.P.
It’s sum of first n terms is given by 2*(2^n-1)/(2-1) = 2^(n+1) – 2 (using G.P. formula)
Sn = n + 2*(2^n – 1)
Sn = 2^(n+1) + n -2
C++
// C++ program to find sum of first n terms #include <bits/stdc++.h> using namespace std; int calculateSum( int n) { // Sn = n*(4*n*n + 6*n - 1)/3 return ( pow (2, n + 1) + n - 2); } // Driver code int main() { // number of terms to be included in sum int n = 4; // find the Sn cout << "Sum = " << calculateSum(n); return 0; } |
Java
// Java program to find // sum of first n terms import java.util.*; class GFG { static int calculateSum( int n) { // Sn = n*(4*n*n + 6*n - 1)/3 return (( int )Math.pow( 2 , n + 1 ) + n - 2 ); } // Driver Code public static void main(String args[]) { // number of terms to // be included in sum int n = 4 ; // find the Sn System.out.println( "Sum = " + calculateSum(n)); } } // This code is contributed // by Kirti_Mangal |
Python
# Python program to find sum # of n terms of the series def calculateSum(n): return ( 2 * * (n + 1 ) + n - 2 ) # Driver Code # number of terms for the sum n = 4 # find the Sn print ( "Sum =" , calculateSum(n)) # This code is contributed # by Surendra_Gangwar |
C#
//C# program to find // sum of first n terms using System; class GFG { static int calculateSum( int n) { // Sn = n*(4*n*n + 6*n - 1)/3 return (( int )Math.Pow(2, n + 1) + n - 2); } // Driver Code public static void Main() { // number of terms to // be included in sum int n = 4; // find the Sn Console.WriteLine( "Sum = " + calculateSum(n)); } } // This code is contributed // by inder_verma.. |
Javascript
<script> // Java script program to find // sum of first n terms function calculateSum( n) { // Sn = n*(4*n*n + 6*n - 1)/3 return (Math.pow(2, n + 1) + n - 2); } // Driver Code // number of terms to // be included in sum let n = 4; // find the Sn document.write( "Sum = " + calculateSum(n)); // This code is contributed by mohan pavan </script> |
PHP
<?php // PHP program to find sum // of first n terms function calculateSum( $n ) { // Sn = n*(4*n*n + 6*n - 1)/3 return (pow(2, $n + 1) + $n - 2); } // Driver code // number of terms to be // included in sum $n = 4; // find the Sn echo "Sum = " , calculateSum( $n ); // This code is contributed // by inder_verma.. ?> |
Sum = 34
Time Complexity: O(log n)
Auxiliary Space: O(log n)
Another Approach: Using recursion
In this approach, we can use a recursive function to generate the series and sum the first n terms of the series.
Steps that were to follow the above approach:
- Initialize the sum variable to 0.
- Define a recursive function that takes the current term, the sum, and the remaining number of terms as arguments.
- If the remaining number of terms is 0, return the sum.
- Add the current term to the sum.
- Multiply the current term by 2 and subtract 1.
- Call the recursive function with the updated current term, sum, and remaining number of terms.
- Return the result of the recursive function.
Below is the code to implement the above steps:
C++
#include <iostream> using namespace std; int sum_of_terms( int current_term, int sum, int n) { if (n == 0) { return sum; } sum += current_term; current_term = current_term * 2 - 1; return sum_of_terms(current_term, sum, n - 1); } int main() { int n = 4; int sum = sum_of_terms(3, 0, n); cout << "Sum =" << sum << endl; return 0; } |
Java
import java.io.*; public class Main { // Recursive function to calculate sum of geometric series public static int sum_of_terms( int current_term, int sum, int n) { // Base case: when n reaches 0, return the sum if (n == 0 ) { return sum; } // Add current term to the sum and calculate the next term sum += current_term; current_term = current_term * 2 - 1 ; // Recursively call the function with the next term and updated sum and n return sum_of_terms(current_term, sum, n - 1 ); } public static void main(String[] args) { int n = 4 ; // Call the recursive function to calculate the sum of geometric series int sum = sum_of_terms( 3 , 0 , n); // Print the result System.out.println( "Sum =" + sum); } } |
Python3
def sum_of_terms(current_term, _sum, n): # Base case: when n reaches 0, return the sum if n = = 0 : return _sum # Add current term to the sum and calculate the next term _sum + = current_term current_term = current_term * 2 - 1 # Recursively call the function with the next term and updated sum and n return sum_of_terms(current_term, _sum, n - 1 ) def main(): n = 4 # Call the recursive function to calculate the sum of the geometric series _sum = sum_of_terms( 3 , 0 , n) # Print the result print ( "Sum =" , _sum) if __name__ = = "__main__" : main() |
C#
using System; class Program { // Recursive function to calculate the sum of terms static int SumOfTerms( int currentTerm, int sum, int n) { // Base case: return the sum when n becomes 0 if (n == 0) { return sum; } // Update the sum and calculate the next term sum += currentTerm; currentTerm = currentTerm * 2 - 1; // Recursive call with updated values return SumOfTerms(currentTerm, sum, n - 1); } static void Main() { // Number of terms int n = 4; // Initial term and sum int initialTerm = 3; int sum = SumOfTerms(initialTerm, 0, n); // Output the sum Console.WriteLine( "Sum = " + sum); } } |
Javascript
function sumOfTerms(currentTerm, sum, n) { // Base case: when n reaches 0, return the sum if (n === 0) { return sum; } // Add current term to the sum and calculate the next term sum += currentTerm; currentTerm = currentTerm * 2 - 1; // Recursively call the function with the next term and updated sum and n return sumOfTerms(currentTerm, sum, n - 1); } function main() { let n = 4; // Call the recursive function to calculate the sum of the geometric series let sum = sumOfTerms(3, 0, n); // Print the result console.log( "Sum =" , sum); } main(); |
Sum =34
Time complexity: O(n)
Space complexity: O(n) (due to the recursion depth)
Contact Us