Given a positive integer, N. Find the sum of the first N term of the series-
1, (1+4), (1+4+42), (1+4+42+43), …., till N terms
Examples:
Input: N = 3
Output: 27Input: N = 5
Output: 453
Approach:
1st term = 1
2nd term = (1 + 4)
3rd term = (1 + 4 + 4 ^ 2)
4th term = (1 + 4 + 4 ^ 2 + 4 ^ 3)
.
.
Nth term = (1 + 4 + 4 ^ 2+….+ 4 ^ (N – 2) + 4 ^(N – 1))
The sequence is formed by using the following pattern. For any value N-
Derivation:
The following series of steps can be used to derive the formula to find the sum of N terms-
The series
can be decomposed as-
-(1)
The equation (1) is in G.P. with
First term a = 1
Common ration r = 4
The sum of N terms in G.P. for r>1 is
Substituting the values of a and r in the above equation, we get-
Thus, the term
The sum of the series 1, (1+4), (1+4+4^{2}), (1+4+4^{2}+4^{3})+….+N terms can be represented as-
-(2)
The equation-
is in G.P. with
First term a = 4
Common ratio r = 4
Applying the formula of sum of G.P.-
-(3)
Substituting equation (3) in equation (2), we get-
-(1)
-(2)
-(3)
Illustration:
Input: N = 3
Output: 11
Explanation:
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sum// of first N termint calcSum(int n){ int a = pow(4, n); return (4 * (a - 1) - 3 * n) / 9;}// Driver Codeint main(){ // Value of N int N = 3; // Function call to calculate // sum of the series cout << calcSum(N); return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to calculate the sum // of first N term static int calcSum(int n) { int a = (int)Math.pow(4, n); return (4 * (a - 1) - 3 * n) / 9; } // Driver Code public static void main(String[] args) { // Value of N int N = 3; // Function call to calculate // sum of the series System.out.print(calcSum(N)); }}// This code is contributed by code_hunt. |
Python3
# Python 3 program for the above approach# Function to calculate the sum# of first N termdef calcSum(n): a = pow(4, n) return (4 * (a - 1) - 3 * n) / 9# Driver Codeif __name__ == "__main__": # Value of N N = 3 # Function call to calculate # sum of the series print(calcSum(N))# This code is contributed by Abhishek Thakur. |
C#
// C# code for the above approachusing System;class GFG{ // Function to calculate the sum // of first N term static int calcSum(int n) { int a = (int)Math.Pow(4, n); return (4 * (a - 1) - 3 * n) / 9; } // Driver Code public static void Main() { // Value of N int N = 3; // Function call to calculate // sum of the series Console.Write(calcSum(N)); }}// This code is contributed by gfgking |
Javascript
<script>// Javascript program to implement// the above approach// Function to calculate the sum// of first N termfunction calcSum(n){ let a = Math.pow(4, n) return (4 * (a - 1) - 3 * n) / 9}// Driver Code// Value of Nlet N = 3// Function call to calculate// sum of the seriesdocument.write(calcSum(N))// This code is contributed by samim2000.</script> |
27
Time Complexity: O(log4n) because using inbuilt pow function
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
