Problem 3 - Applied Discrete Structures

Question

(a) Express the formula \(\sum_{i=1}^{n} \frac{1}{i(i+1)}=\frac{n}{n+1}\) without using summation notation. (b) Verify this formula for \(n=3\). (c) Repeat parts (a) and (b) for \(\sum_{i=1}^{n} i^{3}=\frac{n^{2}(n+1)^{2}}{4}\)

Step-by-Step Solution

Answer

(a) The formula simplifies by telescoping. (b) Verified for \(n=3\). (c) Cube sum matches formula, verified for \(n=3\).

Step 1: Expand the Fraction

Begin by examining the fraction \( \frac{1}{i(i+1)} \). This can be expressed as a difference of fractions by using partial fractions:\[ \frac{1}{i(i+1)} = \frac{1}{i} - \frac{1}{i+1} \].

Step 2: Write Out the Series

Now express the summation \( \sum_{i=1}^{n} \left( \frac{1}{i} - \frac{1}{i+1} \right) \). Expanded, this series looks like: \[ \left( \frac{1}{1} - \frac{1}{2} \right) + \left( \frac{1}{2} - \frac{1}{3} \right) + \ldots + \left( \frac{1}{n} - \frac{1}{n+1} \right) \].

Step 3: Use Telescoping Nature

Observing the expanded series, you'll notice that it is telescoping. Most terms cancel each other out except for the first and last terms, resulting in:\[ 1 - \frac{1}{n+1} = \frac{n}{n+1} \].

Step 4: Verify Part (b) for n=3

Substituting \( n=3 \), compute the series: \[ \sum_{i=1}^{3} \frac{1}{i(i+1)} = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} = \frac{1}{2} + \frac{1}{6} + \frac{1}{12} \].Simplifying the sum gives \( \frac{6+2+1}{12} = \frac{9}{12} = \frac{3}{4} \). Using the formula, \( \frac{3}{4} = \frac{3}{3+1} = \frac{3}{4} \), verify the result matches.

Step 5: Express the Cube Sum Without Summation

Consider \( \sum_{i=1}^{n} i^3 \) and express it with the formula: \[ \sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4} \].This is a known summation result for cubes.

Step 6: Verify Cube Formula for n=3

Calculate \( \sum_{i=1}^{3} i^3 \) directly: \[ 1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36 \].Using the formula \( \frac{3^2 (3+1)^2}{4} = \frac{9 \times 16}{4} = \frac{144}{4} = 36 \). The direct computation matches the formula.

Key Concepts

Telescoping Series

Telescoping series are a fascinating type of summation that involves a lot of cancellation. In these series, when the sequence is expanded, most of the terms cancel each other out, leaving only a few terms. This makes the summation much easier to compute, as seen in the exercise. When we convert the expression \( \frac{1}{i(i+1)} \) into its partial fractions \( \frac{1}{i} - \frac{1}{i+1} \), each consecutive pair of terms will cancel, except the very first and the last terms. This cancellation process simplifies the sum significantly.

For instance, for a given \( n \), the sequence becomes:

• \( \frac{1}{1} - \frac{1}{2} \)
• \( \frac{1}{2} - \frac{1}{3} \)
• ... up to ...
• \( \frac{1}{n} - \frac{1}{n+1} \)

Upon cancellation of intermediate terms, the result is simply \( 1 - \frac{1}{n+1} \), simplifying to \( \frac{n}{n+1} \). This simplicity makes telescoping series useful for proving summation formulas.

Partial Fractions

Partial fraction decomposition is an algebraic technique wherein a complex rational expression is broken down into simpler fractions. This technique is crucial in simplifying the terms in a series to make summation easier. Consider the fraction \( \frac{1}{i(i+1)} \). This can be decomposed as:

• \( \frac{1}{i(i+1)} = \frac{1}{i} - \frac{1}{i+1} \)

By finding a common denominator and comparing terms, this decomposition splits a single fraction into two much simpler terms, making it manageable for use in summation. Partial fractions are particularly helpful when dealing with sequences that can telescope because they reveal the hidden cancellation properties of these series.

This decomposition aids in both algebraic simplification and contributes greatly to the elegance of telescoping series, as each pair of fractions neatly cancels out along the series.

Cube Summation Formula

The cube summation formula is a powerful tool for solving sums of cubes without laboriously calculating each individual cubic term. For an integer \( n \), the formula for the sum of cubes is:

• \( \sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4} \)

This elegant formula states that the sum of the cubes of the first \( n \) natural numbers is equal to the square of the sum of the first \( n \) natural numbers. The formula elegantly packages the entire summation process into one beautiful expression.

Taking \( n=3 \) as an example: the cubic sequence 1, 8, 27 totals to 36. Using the formula, we calculate:

• \( \frac{3^2(3+1)^2}{4} = \frac{9 \times 16}{4} = 36 \)

This verification matches the direct calculation and beautifully illustrates the power of the cube summation formula.

Verification of Algebraic Formulas

Verification of algebraic formulas involves demonstrating that a given algebraic statement holds true for specific values. To verify the provided formula for the sum of a series, you must calculate it directly and compare it with the result obtained using the formula.

For example, when verifying the sum \( \sum_{i=1}^{3} \frac{1}{i(i+1)} \) for \( n=3 \), we add:

• \( \frac{1}{2} + \frac{1}{6} + \frac{1}{12} = \frac{3}{4} \)

This computed sum should match the value derived from the formula \( \frac{n}{n+1} \). Similarly, for verifying the sum of cubes, one calculates the cube of each integer up to \( n \) and checks against the result of the cube formula.

• Direct sum: \( 1^3 + 2^3 + 3^3 = 36 \)
• Formula: \( \frac{3^2 (3+1)^2}{4} = 36 \)

Verification not only confirms the correctness but also gives a deeper insight into the elegance and efficiency of algebraic formulas.