Comprehensive Study Guide on Summations, Products, Big Operators, and Symmetric Power Sums

Fundamentals and Notation of Summations

• Summations serve as the discrete counterparts of continuous integrals, aggregating terms across an explicit or implicit sequence.
• For a sequence of elements $x_a, x_{a+1}, \dots, x_b$, the expansion $x_a + x_{a+1} + \dots + x_b$ is represented compactly using capital sigma ($\Sigma$) notation:   $\sum_{i=a}^b x_i$
• Key components of summation notation:
  • The stretched Greek capital letter sigma indicates the summation operation.
  • The variable $i$ represents the index of summation.
  • The lower value $a$ constitutes the lower bound (or lower limit).
  • The upper value $b$ constitutes the upper bound (or upper limit).
• The operational mechanism mirrors a standard programming for loop: the process iterates sequentially through all integer values of the index $i$ starting at $a$ and ending at $b$ (including both endpoints), evaluating and accumulating the body expression for every iteration.
• Empty Sum Rule: Whenever the upper bound is strictly less than the lower bound ($b < a$), the sum evaluates to zero ($0$):   $\sum_{i=0}^{-5} \frac{2^i \sin(i)}{i^3} = 0$
• The empty sum convention preserves the consistency of algebraic identities at extreme boundary values:
  • For the standard arithmetic identity:     $\sum_{i=1}^n i = \frac{n(n + 1)}{2}$
  • Substituting $n = 0$ gives $\frac{0(1)}{2} = 0$, which accurately reflects an empty sum over $i \in [1, 0]$.
  • Substituting $n = -1$ gives $\frac{-1(0)}{2} = 0$, which matches an empty sum over $i \in [1, -1]$.
  • The identity fails for $n = -2$, as $\frac{-2(-1)}{2} = 1$, whereas the index range from $1$ down to $-2$ is empty and evaluates to $0$.
• Summation notation provides two key benefits:
  • Compactness (laziness): Writing $\sum_{i=0}^n (2i + 1)$ replaces the cumbersome expansion $1 + 3 + 5 + 7 + \dots + (2n + 1)$.
  • Precision: It removes ambiguity regarding intermediate terms and edge conditions.

Formal Recursive Definitions of Finite Sums

• Finite summations can be formally specified via recurrence relations, peeling terms from either boundary:
  • Recurrence peeling the first term:     $\sum_{i=a}^b f(i) = \begin{cases} 0 & \text{if } b < a \\ f(a) + \sum_{i=a+1}^b f(i) & \text{otherwise} \end{cases}$
  • Recurrence peeling the last term:     $\sum_{i=a}^b f(i) = \begin{cases} 0 & \text{if } b < a \\ f(b) + \sum_{i=a}^{b-1} f(i) & \text{otherwise} \end{cases}$
• Computationally, any finite sum can be evaluated recursively by calculating the sum of the first (or last) $n - 1$ terms and adding the single remaining value.

Index Variables, Substitution, and Scope Rules

• Index variable selection:
  • Indices are traditionally denoted by letters such as $i, j, k$.
  • Best practice requires choosing an index variable that does not appear in the external context to prevent variable shadowing and ambiguity.
  • The expression $\sum_{n=0}^n n = \sum_{i=0}^n i$ is mathematically well-defined, but using an independent variable $i$ avoids confusion between the running index and the boundary parameter.
• Index shifting (substitution):
  • An index can be shifted by substituting a new variable, provided the upper and lower limits are transformed accordingly.
  • Example: Substituting $j = i - 1$ transforms the sum:     $\sum_{i=1}^n (i - 1) = \sum_{j=0}^{n-1} j$
• Scope of summation:
  • The scope of the summation operator extends rightward up to the first addition or subtraction symbol that is not enclosed within parentheses or nested inside a larger compound term (such as a fraction numerator).
  • Precedence ambiguity example:     $\sum_{i=1}^n i^2 + 1 = \left(\sum_{i=1}^n i^2\right) + 1 = 1 + \sum_{i=1}^n i^2 \neq \sum_{i=1}^n (i^2 + 1)$
• To prevent misinterpretation, place the summation in explicit parentheses or reposition trailing additive terms to the front.
• Exception for adjacent sums: When adding two distinct sums, such as:   $\sum_{i=1}^n i^2 + \sum_{i=1}^{n^2} i = \left(\sum_{i=1}^n i^2\right) + \left(\sum_{i=1}^{n^2} i\right)$   The presence of the second sigma symbol acts as an unambiguous delimiter indicating the termination of the first summation.

Summations Over Sets and General Predicates

• Summations can aggregate expressions over non-consecutive integers, arbitrary sets, or elements satisfying specific predicates, replacing the traditional upper and lower bounds with a subscript predicate.
• Set-theoretic requirement: The collection of objects satisfying the predicate must form a well-defined set.
• Examples of predicate and set-based sums:
  • Explicit finite set: Summing squares over the set ${3, 5, 7}$:     $\sum_{i \in \{3, 5, 7\}} i^2 = 3^2 + 5^2 + 7^2 = 9 + 25 + 49 = 83$
  • Power set subsets: Summing the cardinalities of all subsets of a given set $S$:     $\sum_{A \subseteq S} |A|$
  • Number-theoretic predicates: Summing the reciprocals of all primes below 1000:     $\sum_{p < 1000, \, p \text{ is prime}} \frac{1}{p}$
  • Pairwise indexing over compound conditions: Summing products over ordered pairs:     $\sum_{1 \le i < j \le n} i j$     This iterates over all unique pairs $(i, j)$ such that $1 \le i < j \le n$, with each distinct pair processed exactly once.
  • Filtered subset sums: Given a defined element $x$ and set $S$:     $\sum_{x \in A \subseteq S} |A|$     This sums the size of every subset $A$ of $S$ that contains $x$.
• Variable identification conventions: A symbol serves as an index variable if it carries no independent meaning outside the summation. When feasible, index symbols appear first within the predicate subscript.
• Well-definedness for finite vs. infinite sets:
  • Finite sets: A sum over a finite set $S$ with cardinality $|S| = n$ is always well-defined. Using a bijection $f: \{0, 1, \dots, n - 1\} \leftrightarrow S$, the sum maps to a standard integer sequence:     $\sum_{i \in S} x_i = \sum_{i=0}^{n-1} x_{f(i)}$
  • Countable infinite sets: For a countably infinite set $S$ with a bijection $f: \mathbb{N} \leftrightarrow S$, the sum can be structured as an infinite series:     $\sum_{i \in S} x_i = \sum_{i=0}^\infty x_{f(i)}$
  • Sign dependency caveat: If the terms $x_i$ have mixed positive and negative signs, conditional convergence implies the resulting sum may vary based on the chosen bijection $f$ (by the Riemann rearrangement theorem). Infinite sums over arbitrary index sets should be avoided unless $\mathbb{N}$ is explicitly established as the canonical ordering.

Unbounded Indices, Conventions, and Infinite Series

• Sums without explicit bounds:
  • When the index domain is obvious from context, bounds may be omitted entirely, leaving only the index subscript (e.g., $\sum_i i^2$). In formal mathematical contexts, this shorthand can be ambiguous.
  • Einstein summation convention: In theoretical physics, tensor equations omit the summation symbol entirely whenever an index appears twice (once as an upper index and once as a lower index), implying summation over the full coordinate range.
• Infinite series:
  • An infinite series is defined as the limit of a sequence of partial sums $s_n$:     $\sum_{i=0}^\infty \frac{1}{i^2} = \lim_{n \to \infty} s_n = \lim_{n \to \infty} \sum_{i=0}^n \frac{1}{i^2}$
  • Formal convergence: The partial sums converge to a limit $x$ if for every real $\epsilon > 0$, there exists an integer $N$ such that for all $n > N$:     $|s_n - x| < \epsilon$
  • Infinite summations serve as the core mathematical basis for generating functions.

Multiple and Nested Summations

• Summations can be nested within one another, producing double, triple, and higher-order multi-dimensional sums.
• Algorithmic interpretation: A double summation corresponds to two nested for loops, iterating over all pairs of indices.
• Formal definition of non-negative integer multiplication using nested sums:   $a \times b \stackrel{\text{def}}{=} \sum_{i=1}^a \sum_{j=1}^b 1$
• Dependent inner limits:
  • Inner summation bounds may depend on the outer summation index:     $\sum_{i=0}^n \sum_{j=0}^i (i + 1)(j + 1)$
  • Step-by-step evaluation for $n = 1$:
  • For $i = 0$: the inner index runs from $j = 0$ to $0$:       $(0 + 1)(0 + 1) = 1$
  • For $i = 1$: the inner index runs from $j = 0$ to $1$:       $(1 + 1)(0 + 1) + (1 + 1)(1 + 1) = (2)(1) + (2)(2) = 2 + 4 = 6$
  • Total accumulated sum:       $1 + 6 = 7$

Algebraic Identities of Summations

• Linearity of the summation operator:
  • Constant factor extraction: Any factor independent of the summation index can be factored out:     $\sum_{i \in S} a x_i = a \sum_{i \in S} x_i$
  • Term splitting: Additive terms within a summation can be separated into independent sums:     $\sum_{i \in S} (x_i + y_i) = \sum_{i \in S} x_i + \sum_{i \in S} y_i$
• Commutativity of independent summations:
  • Provided the bounds of the inner summation do not depend on the outer index, the order of summation can be freely swapped:     $\sum_{i \in S} \sum_{j \in T} x_{ij} = \sum_{j \in T} \sum_{i \in S} x_{ij}$
• Multiplicative product decomposition:
  • The product of two separate summations over independent index sets factors into a double summation of products, and vice versa:     $\left(\sum_{i \in S} x_i\right) \left(\sum_{j \in T} y_j\right) = \sum_{i \in S} \sum_{j \in T} x_i y_j$

Standard Closed-Form Sums and Proof Techniques

• Essential closed-form identities:
  • Constant series:     $\sum_{i=1}^n 1 = n$
  • Arithmetic series:     $\sum_{i=1}^n i = \frac{n(n + 1)}{2}$
  • Finite geometric series (for $r \neq 1$):     $\sum_{i=0}^n r^i = \frac{1 - r^{n+1}}{1 - r}$
• Proof techniques for standard sums:
  • Rigorous proofs for all three identities can be established via mathematical induction on $n$.
  • Carl Friedrich Gauss reverse-summation trick (informal proof for arithmetic series):
  • Write the series forwards and backwards, aligning pairs vertically:       $S = 1 + 2 + 3 + \dots + n$$S = n + (n - 1) + (n - 2) + \dots + 1$
  • Sum the two equations term-by-term:       $2S = (n + 1) + (n + 1) + (n + 1) + \dots + (n + 1) = n(n + 1)$
  • Solving for $S$ yields:       $S = \frac{n(n + 1)}{2}$
  • Derivation of the geometric series formula via infinite series subtraction:
  • For $|r| < 1$, define the infinite sum $S = \sum_{i=0}^\infty r^i$.
  • Multiplying by $r$ shifts all terms: $rS = \sum_{i=0}^\infty r^{i+1} = \sum_{i=1}^\infty r^i$.
  • Subtracting $rS$ from $S$ telescopes all higher-order terms:       $S - rS = r^0 = 1 \implies S(1 - r) = 1 \implies S = \frac{1}{1 - r}$
  • The finite sum up to index $n$ is obtained by subtracting the infinite tail starting at index $n + 1$:       $\sum_{i=0}^n r^i = \sum_{i=0}^\infty r^i - r^{n+1} \sum_{i=0}^\infty r^i = \frac{1}{1 - r} - \frac{r^{n+1}}{1 - r} = \frac{1 - r^{n+1}}{1 - r}$
  • While derived assuming $|r| < 1$, the resulting rational expression $\frac{1 - r^{n+1}}{1 - r}$ holds algebraically for all values $r \neq 1$, including $r > 1$.
  • At $r = 1$, evaluating the rational formula causes division by zero ($0/0$); the sum simplifies directly to the constant series $\sum_{i=0}^n 1 = n + 1$.
• Reference literature: Comprehensive catalogs of summation formulas are provided in Kenneth Rosen's discrete mathematics texts and in Concrete Mathematics by Graham, Knuth, and Patashnik, particularly within discussions of generating functions.

The Guess-and-Verify Method

• When formal manipulation fails, closed-form expressions can be deduced using the "guess but verify" sequence identification strategy:
  1. Calculate explicit numerical values of the sum for small consecutive values of the upper limit $n$.
  2. Identify the underlying pattern or closed-form polynomial.
  3. Prove the conjectured closed form rigorously using mathematical induction on $n$.
• Worked example: Sum of the first $n$ odd integers:   $S(n) = \sum_{k=1}^n (2k - 1)$
  • Generate a table of empirical values:
  • For $n = 0$: $S(0) = 0$
  • For $n = 1$: $S(1) = 1$
  • For $n = 2$: $S(2) = 1 + 3 = 4$
  • For $n = 3$: $S(3) = 1 + 3 + 5 = 9$
  • For $n = 4$: $S(4) = 1 + 3 + 5 + 7 = 16$
  • For $n = 5$: $S(5) = 1 + 3 + 5 + 7 + 9 = 25$
  • Conjecture: The sequence of sums matches square numbers: $S(n) = n^2$.
  • Inductive verification:
  • Base case: For $n = 0$, $S(0) = 0^2 = 0$, which holds.
  • Inductive step: Assume $S(n - 1) = (n - 1)^2$ holds for $n \ge 1$. Then:       $S(n) = S(n - 1) + (2n - 1) = (n - 1)^2 + 2n - 1 = n^2 - 2n + 1 + 2n - 1 = n^2$
  • The conjecture $S(n) = n^2$ is verified for all integers $n \ge 0$.

Asymptotic Estimation Strategies in Algorithm Analysis

• In algorithmic complexity analysis, exact summation evaluation is rarely necessary because results are expressed using asymptotic notation ($\Theta, O, \Omega$). Approximation strategies streamline this analysis.
• Strategy 1: Factor out constants:
  • Pull out all terms that do not contain the summation index:     $\sum_{i=1}^n \frac{n}{i} = n \sum_{i=1}^n \frac{1}{i} = n H_n = \Theta(n \log(n))$
• Strategy 2: Bound using standard known series:
  • Geometric series:     $\sum_{i=0}^n x^i = \frac{1 - x^{n+1}}{1 - x}, \quad \sum_{i=0}^\infty x^i = \frac{1}{1 - x}$
  • Identified by a constant ratio between adjacent terms.
  • Dominant term principle: Whenever the common ratio $x$ is a constant not equal to 1, the sum is asymptotically proportional to its largest single term ($\Theta(\text{largest term})$):
    • Growing geometric series ($x > 1$):         $\sum_{i=1}^n 2^i = \Theta(2^n) \quad (\text{exact: } 2^{n+1} - 2)$
    • Decaying geometric series ($x < 1$):         $\sum_{i=1}^n 2^{-i} = \Theta(1) \quad (\text{exact: } 1 - 2^{-n})$
  • This dominant-term property provides the underlying mathematical foundation for the Master Theorem in solving divide-and-conquer recurrences.
  • Constant series:     $\sum_{i=1}^n 1 = n$
  • Arithmetic series:
  • Identified by a constant difference between adjacent terms.
  • Base form: $\sum_{i=1}^n i = \frac{n(n + 1)}{2}$, conceptually remembered as $n \times (\text{average value } \frac{n+1}{2})$.
  • General arithmetic progression:       $\sum_{i=1}^n (ai + b) = a \sum_{i=1}^n i + \sum_{i=1}^n b = \frac{a n(n + 1)}{2} + b n$
  • Harmonic series:
  • The $n$-th harmonic number is defined as $H_n = \sum_{i=1}^n \frac{1}{i}$.
  • Asymptotic behavior: $H_n = \Theta(\log(n))$, leading to $n H_n = \Theta(n \log(n))$.
• Strategy 3: Bound part of the sum (sum splitting):
  • Approximate sums within constant factors by partitioning the index range.
  • Example: Bounding $\sum_{i=1}^n i^3$ without finding its closed form:
  • Upper bound: Replace every term with the maximum term $n^3$:       $\sum_{i=1}^n i^3 \le \sum_{i=1}^n n^3 = n \cdot n^3 = n^4 = O(n^4)$
  • Lower bound: Sum only across the upper half of the range ($i = n/2$ to $n$) and replace each term with the minimum value in that subrange ($(n/2)^3$):       $\sum_{i=1}^n i^3 \ge \sum_{i=n/2}^n i^3 \ge \sum_{i=n/2}^n \left(\frac{n}{2}\right)^3 = \left(\frac{n}{2}\right) \left(\frac{n^3}{8}\right) = \frac{n^4}{16} = \Omega(n^4)$
  • Combining both bounds proves $\sum_{i=1}^n i^3 = \Theta(n^4)$.
• Strategy 4: Continuous integration bounds:
  • For any monotonically non-decreasing function $f(x)$, the sum is bounded above and below by continuous definite integrals:     $\int_{a-1}^b f(x)\,dx \le \sum_{i=a}^b f(i) \le \int_a^{b+1} f(x)\,dx$
  • This technique yields tight $\Theta$ bounds for almost all monotonic functions in algorithm analysis.
• Strategy 5: Grouping terms (condensation):
  • Terms can be aggregated into dyadic blocks to verify convergence or divergence.
  • Divergence proof for the harmonic series via grouping powers of two:     $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \dots \ge 1 + \frac{1}{2} + \left(\frac{1}{4} + \frac{1}{4}\right) + \left(\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}\right) + \dots$$1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \dots = \infty$
• Strategy 6: Oddity sums (mixed polynomial-exponential series):
  • Evaluation of $\sum_{i=1}^n a^i i$ across different parameter ranges:
  • Subcritical ($a < 1$): The series converges to $\Theta(1)$. The infinite closed form provides a constant upper bound:       $\sum_{i=1}^\infty a^i i = \frac{a}{(1 - a)^2}$
  • Critical ($a = 1$): Reduces to the standard arithmetic series $\sum_{i=1}^n i = \Theta(n^2)$.
  • Supercritical ($a > 1$): The largest term dominates, giving $\Theta(a^n n)$.
  • Proof of the upper bound $O(a^n n)$ for $a > 1$ by index reversal:       $\sum_{i=0}^{n-1} a^{n-i}(n - i) \le \sum_{i=0}^{n-1} a^{n-i} n \le \frac{a^n n}{1 - a^{-1}} = O(a^n n)$
• General principles for algorithm analysis sums:
  • Most sums match $\sum_{i=1}^n f(i)$ where:
  • Exponential growth ($f(n)$ is exponential): The sum is bounded by a geometric series and is dominated by the largest term: $\Theta(f(n))$.
  • Polynomial growth ($f(n)$ is polynomial): The function satisfies $f(n/2) = \Theta(f(n))$, and the sum scales as $\Theta(n f(n))$, verified by the lower bound $\sum_{i=n/2}^n f(i) = \Omega(n f(n))$.
  • When exact closed forms are required rather than asymptotic bounds, generating functions provide the primary analytical framework.

Product Operators and Factorials

• Capital Pi notation ($\Pi$) represents repeated multiplication, using index limits identical to summation notation:   $\prod_{i=a}^b x_i = x_a \cdot x_{a+1} \dotsm x_b$
• Factorial function definition for non-negative integers:   $n! \stackrel{\text{def}}{=} \prod_{i=1}^n i = 1 \cdot 2 \dotsm n$
• Identity element conventions for empty operations:
  • An empty summation evaluates to $0$ (the identity element for addition).
  • An empty product evaluates to $1$ (the identity element for multiplication).
  • Mathematical rationale: The empty operation must return the identity element to preserve algebraic homomorphisms over disjoint partitioned sets $A \cap B = \emptyset$:     $\sum_{i \in A} f(i) + \sum_{i \in B} f(i) = \sum_{i \in A \cup B} f(i)$$\left(\prod_{i \in A} f(i)\right) \cdot \left(\prod_{i \in B} f(i)\right) = \prod_{i \in A \cup B} f(i)$
  • If an empty product evaluated to anything other than $1$, special-case logic would be needed whenever $A = \emptyset$ or $B = \emptyset$.
  • A direct consequence of the empty product definition is:     $0! = \prod_{i=1}^0 i = 1$

Generalized Aggregate Operators

• The indexing mechanisms used in $\sum$ and $\prod$ generalize across associative and commutative mathematical operations:
  • Big AND (Universal Quantification):     $\bigwedge_{x \in S} P(x) \equiv P(x_1) \land P(x_2) \land \dots \equiv \forall x \in S : P(x)$
  • Evaluates to True over an empty set ($S = \emptyset$), as True is the identity element for logical conjunction ($P \land \text{True} \equiv P$).
  • Big OR (Existential Quantification):     $\bigvee_{x \in S} P(x) \equiv P(x_1) \lor P(x_2) \lor \dots \equiv \exists x \in S : P(x)$
  • Evaluates to False over an empty set ($S = \emptyset$), as False is the identity element for logical disjunction ($P \lor \text{False} \equiv P$).
  • Big Intersection:     $\bigcap_{i=1}^n A_i = A_1 \cap A_2 \cap \dots \cap A_n$
  • Over an empty collection of sets, the intersection is undefined in general set theory because no universal set exists to serve as the absolute identity element.
  • Big Union:     $\bigcup_{i=1}^n A_i = A_1 \cup A_2 \cup \dots \cup A_n$
  • Over an empty index set, this evaluates to the identity element for set union, which is the empty set ($\emptyset$).

System of Power Sum Equations and Newton's Identities

• Problem statement:
  • Given a system of equations defining the first three power sums of variables $a, b, c$:     $a + b + c = 4$$a^2 + b^2 + c^2 = 10$$a^3 + b^3 + c^3 = 22$
  • Objective: Determine the exact value of the fourth power sum:     $a^4 + b^4 + c^4 = ?$
• Formulation using symmetric polynomials:
  • Define the power sums for the three-variable set $S = \{a, b, c\}$:     $p_k = \sum_{x \in S} x^k = a^k + b^k + c^k$
  • The system provides:     $p_1 = 4$$p_2 = 10$$p_3 = 22$
  • We seek the value of $p_4$.
  • Define the elementary symmetric polynomials:     $e_1 = a + b + c$$e_2 = ab + bc + ca$$e_3 = abc$
• Step-by-step solution via Newton's sums:
  • Determine $e_1$:     $e_1 = p_1 = 4$
  • Determine $e_2$ using the binomial expansion of $p_1^2$:     $(a + b + c)^2 = a^2 + b^2 + c^2 + 2(ab + bc + ca)$$e_1^2 = p_2 + 2e_2$$4^2 = 10 + 2e_2 \implies 16 = 10 + 2e_2 \implies 2e_2 = 6 \implies e_2 = 3$
  • Determine $e_3$ using Newton's identity for $k = 3$:
  • The variables $a, b, c$ are the roots of the monic characteristic cubic polynomial:       $P(x) = (x - a)(x - b)(x - c) = x^3 - e_1 x^2 + e_2 x - e_3 = 0$
  • Summing this polynomial over all three roots $x \in \{a, b, c\}$ gives Newton's relation:       $p_3 - e_1 p_2 + e_2 p_1 - 3e_3 = 0$
  • Substitute known values into the relation:       $22 - (4)(10) + (3)(4) - 3e_3 = 0$$22 - 40 + 12 - 3e_3 = 0$$-6 - 3e_3 = 0 \implies 3e_3 = -6 \implies e_3 = -2$
  • Calculate $p_4$ using Newton's identity for $k = 4$:
  • Multiply the cubic characteristic equation by $x$:       $x^4 - e_1 x^3 + e_2 x^2 - e_3 x = 0$
  • Sum over all roots $x \in \{a, b, c\}$:       $p_4 - e_1 p_3 + e_2 p_2 - e_3 p_1 = 0$
  • Isolate $p_4$:       $p_4 = e_1 p_3 - e_2 p_2 + e_3 p_1$
  • Substitute the computed values ($e_1 = 4$, $p_3 = 22$, $e_2 = 3$, $p_2 = 10$, $e_3 = -2$, $p_1 = 4$):       $p_4 = (4)(22) - (3)(10) + (-2)(4)$$p_4 = 88 - 30 - 8 = 50$
• Explicit root extraction and verification:
  • Characteristic polynomial:     $x^3 - 4x^2 + 3x + 2 = 0$
  • Factoring by inspecting rational roots:
  • Testing $x = 2$: $2^3 - 4(2^2) + 3(2) + 2 = 8 - 16 + 6 + 2 = 0$, confirming $x = 2$ is a root.
  • Polynomial division yields:       $(x - 2)(x^2 - 2x - 1) = 0$
  • Quadratic formula solution for $x^2 - 2x - 1 = 0$:       $x = \frac{2 \pm \sqrt{(-2)^2 - 4(1)(-1)}}{2} = \frac{2 \pm \sqrt{8}}{2} = 1 \pm \sqrt{2}$
  • Root assignments:     $a = 2, \quad b = 1 + \sqrt{2}, \quad c = 1 - \sqrt{2}$
  • Term-by-term power evaluations:
  • First powers:       $a = 2$$b = 1 + \sqrt{2}$$c = 1 - \sqrt{2}$$p_1 = 2 + (1 + \sqrt{2}) + (1 - \sqrt{2}) = 4$
  • Second powers:       $a^2 = 4$$b^2 = (1 + \sqrt{2})^2 = 1 + 2\sqrt{2} + 2 = 3 + 2\sqrt{2}$$c^2 = (1 - \sqrt{2})^2 = 1 - 2\sqrt{2} + 2 = 3 - 2\sqrt{2}$$p_2 = 4 + (3 + 2\sqrt{2}) + (3 - 2\sqrt{2}) = 10$
  • Third powers:       $a^3 = 8$$b^3 = (1 + \sqrt{2})^3 = 1 + 3\sqrt{2} + 6 + 2\sqrt{2} = 7 + 5\sqrt{2}$$c^3 = (1 - \sqrt{2})^3 = 1 - 3\sqrt{2} + 6 - 2\sqrt{2} = 7 - 5\sqrt{2}$$p_3 = 8 + (7 + 5\sqrt{2}) + (7 - 5\sqrt{2}) = 22$
  • Fourth powers:       $a^4 = 2^4 = 16$$b^4 = (3 + 2\sqrt{2})^2 = 9 + 12\sqrt{2} + 8 = 17 + 12\sqrt{2}$$c^4 = (3 - 2\sqrt{2})^2 = 9 - 12\sqrt{2} + 8 = 17 - 12\sqrt{2}$$p_4 = 16 + (17 + 12\sqrt{2}) + (17 - 12\sqrt{2}) = 16 + 34 = 50$
  • The fourth power sum evaluates directly to $50$.