A B C D E F G H I
Solution 1
Implement as given in the problem using a loop. The time complexity is O ( N ) \mathcal O(N) O ( N ) .
Code (C++)
#include <iostream>
using namespace std;
int main ()
{
int N;
cin >> N;
int sum_1 = 0 , sum_3 = 0 ;
for (int i = 1 ; i <= N; i++)
{
sum_1 += i;
sum_3 += i * i * i;
}
cout << sum_1 << endl;
cout << sum_1 * sum_1 << endl;
cout << sum_3 << endl;
}
Code (Python)
def main ():
N = int (input ())
print (sum (range (1 , N+1 )))
print (sum (range (1 , N+1 ))**2 )
print (sum (i**3 for i in range (1 , N+1 )))
if __name__ == '__main__' :
main()
Solution 2
1 + 2 + ⋯ + N = N ( N + 1 ) 2 1+2+\cdots+N = \frac{N(N+1)}{2} 1 + 2 + ⋯ + N = 2 N ( N + 1 ) and 1 3 + 2 3 + ⋯ + N 3 = ( 1 + 2 + ⋯ + N ) 2 = ( N ( N + 1 ) 2 ) 2 1^3 + 2^3 + \cdots + N^3 = (1+2+\cdots+N)^2 = {\left(\frac{N(N+1)}{2}\right)}^2 1 3 + 2 3 + ⋯ + N 3 = ( 1 + 2 + ⋯ + N ) 2 = ( 2 N ( N + 1 ) ) 2 holds. The time complexity is O ( 1 ) \mathcal O (1) O ( 1 ) .
Code (C++)
#include <iostream>
using namespace std;
int main ()
{
int N;
cin >> N;
cout << N * (N + 1 ) / 2 << endl;
cout << (N * (N + 1 ) / 2 ) * (N * (N + 1 ) / 2 ) << endl;
cout << (N * (N + 1 ) / 2 ) * (N * (N + 1 ) / 2 ) << endl;
}
Code (Python)
def main ():
N = int (input ())
print (N * (N + 1 ) // 2 )
print ((N * (N + 1 ) // 2 ) ** 2 )
print ((N * (N + 1 ) // 2 ) ** 2 )
if __name__ == '__main__' :
main()
증명
To prove 1 + 2 + ⋯ + N = N ( N + 1 ) 2 1+2+\cdots+N = \frac{N(N+1)}{2} 1 + 2 + ⋯ + N = 2 N ( N + 1 ) , let's calculate 2 × ( 1 + 2 + ⋯ + N ) 2 \times (1 + 2+ \cdots + N) 2 × ( 1 + 2 + ⋯ + N ) .
When adding two sequences of ( 1 + 2 + ⋯ + N ) (1+2+\cdots+N) ( 1 + 2 + ⋯ + N ) , keep one sequence as it is, and reverse the other before adding. Then, upon inspecting each sum, combining 1 1 1 with N N N yields N + 1 N+1 N + 1 , combining 2 2 2 with N − 1 N−1 N − 1 yields N + 1 N+1 N + 1 , and so on, until combining N N N with 1 1 1 also gives N + 1 N+1 N + 1 . Hence, the total is equivalent to adding N + 1 N+1 N + 1 a total of N N N times, which is N ( N + 1 ) N(N+1) N ( N + 1 ) .
Mathematically:
2 × ( 1 + 2 + ⋯ + N ) = ( 1 + 2 + ⋯ + N ) + ( N + ( N − 1 ) + ⋯ + 1 ) = ( ( 1 + N ) + ( 2 + ( N − 1 ) ) + ⋯ + ( N + 1 ) ) = ( ( N + 1 ) + ( N + 1 ) + ⋯ + ( N + 1 ) ) = N ( N + 1 ) \begin{align*}
& \ 2 \times (1 + 2 + \cdots + N) \\
= & \ (1 + 2 + \cdots + N) + (N + (N-1) + \cdots + 1) \\
= & \ ((1+N) + (2+(N-1)) + \cdots + (N+1)) \\
= & \ ((N+1) + (N+1) + \cdots+ (N+1)) \\
= & \ N(N+1)
\end{align*} = = = = 2 × ( 1 + 2 + ⋯ + N ) ( 1 + 2 + ⋯ + N ) + ( N + ( N − 1 ) + ⋯ + 1 ) (( 1 + N ) + ( 2 + ( N − 1 )) + ⋯ + ( N + 1 )) (( N + 1 ) + ( N + 1 ) + ⋯ + ( N + 1 )) N ( N + 1 )
Let's now prove the slightly more challenging relationship ( 1 + 2 + ⋯ + N ) 2 = 1 3 + 2 3 + ⋯ + N 3 (1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3 ( 1 + 2 + ⋯ + N ) 2 = 1 3 + 2 3 + ⋯ + N 3 . We will demonstrate that both expressions have the same value for N = 1 N=1 N = 1 , and the difference between the values of the expressions for N = i − 1 N=i-1 N = i − 1 and N = i N=i N = i are the same. This will prove the two expressions are equivalent. For N = 1 N = 1 N = 1 , both expressions equal 1. Let's now look at the difference between the two expressions:
Utilizing the identity a 2 − b 2 = ( a − b ) ( a + b ) a^2 - b^2 = (a-b)(a+b) a 2 − b 2 = ( a − b ) ( a + b ) :
( 1 + 2 + ⋯ + i ) 2 − ( 1 + 2 + ⋯ + ( i − 1 ) 2 ) = ( i ( i + 1 ) 2 ) 2 − ( i ( i − 1 ) 2 ) 2 = ( i ( i + 1 ) 2 − i ( i − 1 ) 2 ) × ( i ( i + 1 ) 2 + i ( i − 1 ) 2 ) = ( i ( ( i + 1 ) − ( i − 1 ) ) 2 ) × ( i ( ( i + 1 ) + ( i − 1 ) ) 2 ) = ( i × 2 2 ) × ( i × 2 i 2 ) = i × i 2 = i 3 \begin{align*}
& \ (1+2+\cdots+i)^2 - (1+2+\cdots+(i-1)^2) \\
= & \ \left(\frac{i(i+1)}{2}\right)^2 - \left(\frac{i(i-1)}{2}\right)^2 \\
= & \ \left(\frac{i(i+1)}{2} - \frac{i(i-1)}{2}\right) \times \left(\frac{i(i+1)}{2} + \frac{i(i-1)}{2}\right) \\
= & \ \left(\frac{i((i+1)-(i-1))}{2}\right) \times \left(\frac{i((i+1)+(i-1))}{2}\right) \\
= & \ \left(\frac{i \times 2}{2} \right) \times \left(\frac{i \times 2i}{2} \right) \\
= & \ i \times i^2 = i^3
\end{align*} = = = = = ( 1 + 2 + ⋯ + i ) 2 − ( 1 + 2 + ⋯ + ( i − 1 ) 2 ) ( 2 i ( i + 1 ) ) 2 − ( 2 i ( i − 1 ) ) 2 ( 2 i ( i + 1 ) − 2 i ( i − 1 ) ) × ( 2 i ( i + 1 ) + 2 i ( i − 1 ) ) ( 2 i (( i + 1 ) − ( i − 1 )) ) × ( 2 i (( i + 1 ) + ( i − 1 )) ) ( 2 i × 2 ) × ( 2 i × 2 i ) i × i 2 = i 3
The difference between 1 3 + 2 3 + ⋯ + ( i − 1 ) 3 1^3 + 2^3 + \cdots + (i-1)^3 1 3 + 2 3 + ⋯ + ( i − 1 ) 3 and 1 3 + 2 3 + ⋯ + i 3 1^3 + 2^3 + \cdots + i^3 1 3 + 2 3 + ⋯ + i 3 is also i 3 i^3 i 3 , so the two expressions must indeed be equivalent.
There's also a visual method to prove this .