Sum of first n term of Series 3, 5, 9, 17, 33….

0 0 4 minutes read

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

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>

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..

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..
?>

Output:

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);
    }
}

Time complexity: O(n)
Space complexity: O(n) (due to the recursion depth)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!