Finding the Sum of the First N Integers

 Formula Derivation of the Sum of the first n integers.

First Method:

Suppose we need to find the sum of the first n positive integers. Then, this can be written mathematically as:

\[ S_{n} = \sum_{i=1}^{n} i \]

\[ S_{n} = 1 + 2 + 3 + \cdot \cdot \cdot + n \] 

but the above expression can also be written as (backwards):

\[ S_{n} = n + (n-1) + (n-2) + \cdot \cdot \cdot + 1 \]

Summing the two equations above: 

\[2S_{n} = (n+1) + (n+1) + ... + (n+1) \]

\[2S_{n} = n (n+1) \]

\[ S_{n} = \dfrac{n(n+1)}{2} \]

 


Second Method:

\[ S_{n} = 1 + 2 + 3 + \cdot \cdot \cdot + n \]

Writing in sequence form:

\[ S_{1} = 1  \]

\[ S_{2} = 1 + 2 = 3 \]

\[ S_{3} = 1 + 2 + 3 = 6 \]

\[ S_{4} = 1 + 2 + 3 + 4 = 10 \]

\[ \cdot \]

\[ \cdot \]

\[ \cdot \]

\[ Seq = 1, 3, 6, 10, 15, ..., \sum_{i=1}^{n} i  \] 

Note that the difference between each consecutive sequence is:

\[ 1^{st}difference = 2, 3, 4, 5, 6, \cdot \cdot \cdot \]

Since the difference is not constant, we take the difference of the difference until we get a constant value

\[ 2^{nd}difference = 1,1,1,1, \cdot \cdot \cdot \]

Note that we had to difference twice to obtain a constant value, therefore the polynomial order of the sequence is 2. (If we had to difference once to obtain a constant value, then the polynomial order of the sequence will be 1)

\[ Seq = 1, 3, 6, 10, 15, ..., \sum_{i=1}^{n} i   \equiv An^2 + Bn + C \]

When n=1,

\[ 1 = A + B + C \]

When n = 2,

\[ 3 = 4A + 2B + C \]

When n=3,

\[ 6 = 9A + 3B + C \]

Solving the three equations above simultaneously, 

\[ A= \dfrac{1}{2}, B=\dfrac{1}{2}, C=0 \]

Substituting:

\[ Seq = 1, 3, 6, 10, 15, ..., \sum_{i=1}^{n} i   \equiv \dfrac{1}{2}n^2 + \dfrac{1}{2}n + 0 \]

\[ S_{n} = \dfrac{1}{2}n^2 + \dfrac{1}{2}n + 0 = \dfrac{n(n+1)}{2} \]


Comments

Post a Comment

Popular posts from this blog

Understanding Hashing

Understanding Hashing: A Key Cryptographic Technique   What is Hashing?   Hashing is a cryptographic technique that takes an input of variable length and produces a fixed-length output, often represented in hexadecimal format. It is a one-way operation, meaning the original input cannot be easily derived from the output.  Why is Hashing Useful?   Hashing serves as a cornerstone of data security, particularly for:  Password protection: Hashing secures passwords, ensuring they remain unreadable even if a database is breached. Techniques like salting (adding random data to hashes) further enhance security by thwarting attacks like rainbow table attacks.  Blockchain security: Hashing is integral to blockchain technology, such as Bitcoin, where SHA-256 ensures the integrity and security of transactions and blocks.  Characteristics of Hashing  Irreversibility : Hash functions should be computationally infeasible to reverse. For example, given the hash b...
Read more

Differential of e^{ax} proof

  Differential of \( e^{ax}\) let \( y = e^{ax}\) Taking the natural log on both sides: \[\ln y = \ln e^{ax}\] Apply one of the logarithm rules: \[\ln y = ax \ln e \] but \[\ln e = 1 \] \[\ln y = ax\] Taking the differential with respect to x: (Remember: y is a function of x therefore after differentiating we multiply by the derivative) \[\dfrac{1}{y} \dfrac{dy}{dx} = a \] \[\dfrac{dy}{dx} = ay\] but \(y = e^{ax}\) \[\dfrac{dy}{dx} = ae^{ax}\]  
Read more