Question

Prove that \(\sum_{i=j}^{n}\left(\begin{array}{l}i \\\ j\end{array}\right)=\left(\begin{array}{c}n+1 \\ j+1\end{array}\right)\). In addition to an inductive proof, there is a nice "story" proof of this formula. It is well worth trying to figure out both proofs.

Short answer

The identity is proven using induction and a combinatorial argument.

Step-by-step solution

Understand the Identity

The expression \(\sum_{i=j}^{n}\binom{i}{j}\) represents the sum of binomial coefficients where the upper index ranges from \(j\) to \(n\), while the lower index is constant at \(j\). We want to prove that this sum equals \(\binom{n+1}{j+1}\), which is another binomial coefficient.

Base Case for Inductive Proof

Consider the simplest case where \(n=j\). This gives us \(\sum_{i=j}^{j}\binom{i}{j} = \binom{j}{j}\), which simplifies to \(1\). On the other hand, \(\binom{n+1}{j+1} = \binom{j+1}{j+1}\), which is also 1. Thus, the base case holds true.

Inductive Step

Assume the formula \(\sum_{i=j}^{n}\binom{i}{j} = \binom{n+1}{j+1}\) holds for \(n = k\). Now, we show it holds for \(n = k+1\). The expression becomes \(\sum_{i=j}^{k+1}\binom{i}{j}\), which can be broken down as \(\sum_{i=j}^{k}\binom{i}{j} + \binom{k+1}{j}\). According to our inductive hypothesis, \(\sum_{i=j}^{k}\binom{i}{j} = \binom{k+1}{j+1}\). Therefore, the expression is \(\binom{k+1}{j+1} + \binom{k+1}{j}\).

Simplify with Pascal's Identity

Using Pascal's Identity, \(\binom{k+1}{j+1} + \binom{k+1}{j} = \binom{k+2}{j+1}\). This matches the right-hand side of our original formula for \(n=k+1\), \(\binom{(k+1)+1}{j+1} = \binom{k+2}{j+1}\). Thus, the inductive step is verified.

Story Proof Using Combinatorial Argument

Consider choosing \(j+1\) objects out of \(n+1\). Split the process into two cases: either the object is the first one among the \(j+1\) objects chosen, or it is not. If not, the choice reduces to selecting \(j+1\) objects from the remaining \(n\) elements, counted as \(\binom{n}{j+1}\). If it is the first selected, choose the remaining \(j\) from \(n\) elements, counted as \(\sum_{i=j}^{n}\binom{i}{j}\). Combining these gives \(\binom{n+1}{j+1}\), matching the identity.

Key concepts

Inductive Proof

An inductive proof is a powerful technique used for demonstrating the truth of a statement, especially for expressions involving natural numbers. It consists of two main parts:

• Base Case: We show that the statement holds true for the initial value, typically the smallest possible value of the variables involved. In this exercise, we take the base case as when \(n = j\), leading to \(\binom{j}{j} = 1\), which matches the identity we need to prove.
• Inductive Step: We assume the statement is true for some arbitrary value \(n = k\), called the inductive hypothesis. Then, we show that if it holds for \(n = k\), it must also hold for \(n = k+1\). Here, our task is to show \(\sum_{i=j}^{k+1}\binom{i}{j} = \binom{k+2}{j+1}\).

The inductive proof confirms the identity is true for all \(n\) greater than or equal to \(j\), given it holds for our base case and continues to hold with the inductive step.

Pascal's Identity

Pascal's Identity is a fundamental property of binomial coefficients. It states that for any integers \(n\) and \(k\), \(\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}\). This identity is often used to simplify expressions involving binomial coefficients.

In the context of our given problem, during the inductive step of the proof, we used Pascal's Identity as follows:

• We had \(\binom{k+1}{j+1} + \binom{k+1}{j}\).
• By applying Pascal's Identity, this expression simplifies to \(\binom{k+2}{j+1}\).

This step confirms that the expression is equivalent to the desired form \(\binom{n+1}{j+1}\) when moving from \(n=k\) to \(n=k+1\).

Pascal's Identity is very useful in combinatorics and is also visually represented in Pascal's Triangle, where each number is the sum of the two numbers directly above it.

Combinatorial Argument

A combinatorial argument provides an intuitive way to understand identities in combinatorics by considering the problem as counting occurrences or situations.

In this specific problem, we can use a 'story' to showcase the identity. Imagining it through a selection process:

• We must select \(j+1\) objects from \(n+1\) objects. If the first object is included in the selection, then the task reduces to choosing the remaining \(j\) objects from the \(n\) remaining ones, giving us the summation \(\sum_{i=j}^{n}\binom{i}{j}\).
• Alternatively, if the first object is not in our selection, we directly choose\(j+1\) from the remaining \(n\) objects, counted as \(\binom{n}{j+1}\).

Combining these cases ensures every scenario is covered, leading to the total count being \(\binom{n+1}{j+1}\). This type of reasoning not only verifies the identity but also deepens understanding of why these mathematical expressions hold true.