Question

Show that Fermat's rule, $$ N\left(\begin{array}{c} N+k \\ k \end{array}\right)=(k+1)\left(\begin{array}{c} N+k \\ k+1 \end{array}\right) $$ is equivalent to $$ N \sum_{j=k-1}^{N+k-1}\left(\begin{array}{c} j \\ k-1 \end{array}\right)=(k+1) \frac{N(N+1) \cdots(N+k)}{(k+1) !} $$ and also to $$ \sum_{j=1}^{N} \frac{j(j+1) \cdots(j+k-1)}{k !}=\frac{N(N+1) \cdots(N+k)}{(k+1) !} $$

Short answer

Question: Prove the equivalence between Fermat's rule, given by $$ N\left(\begin{array}{c} N+k \\\ k \end{array}\right)=(k+1)\left(\begin{array}{c} N+k \\\ k+1 \end{array}\right) $$ and $$ \sum_{j=1}^{N} \frac{j(j+1) \cdots(j+k-1)}{k !}=\frac{N(N+1) \cdots(N+k)}{(k+1) !} $$ Answer: The proof involves re-writing both equations using combinatorial notation, simplifying the sums, and showing their equivalence. To prove the equivalence, we first transform the given equations and show that the first equation is equivalent to the second equation. Then, we transform the third equation and compare it with the transformed second equation, finding that they are also equivalent once we distribute N inside the sum. Thus, Fermat's rule is equivalent to both the second and the third provided equations, completing the proof.

Step-by-step solution

Understanding Fermat's rule and its notations

Fermat's rule involves combinatorial notation, which means we're dealing with binomial coefficients. The notation \(\left(\begin{array}{c} j \\ k \end{array}\right)\) denotes the combination of choosing \(k\) elements from a set of \(j\) elements, also written as \(jCk\) or \(C(j,k)\), and calculated as \(\frac{j!}{k!(j-k)!}\), where "!" represents the factorial of a number.

Re-writing the given equation using combinatorics

We are given Fermat's rule in the form: $$ N\left(\begin{array}{c} N+k \\\ k \end{array}\right)=(k+1)\left(\begin{array}{c} N+k \\\ k+1 \end{array}\right) $$ Now, we will rewrite both sides of this equation using the formula for binomial coefficients: $$ N\frac{(N+k)!}{k!(N!)}=(k+1)\frac{(N+k)!}{(k+1)!(N-1)!} $$

Proving equivalence of the first and second equations

We will now work on proving that the equation above is equivalent to the second given equation: $$ N \sum_{j=k-1}^{N+k-1}\left(\begin{array}{c} j \\\ k-1 \end{array}\right)=(k+1) \frac{N(N+1) \cdots(N+k)}{(k+1) !} $$ Let's re-write the second equation with binomial coefficients and see if we can simplify it to look like the first equation. $$ N \sum_{j=k-1}^{N+k-1}\frac{j!}{(k-1)!(j-k+1)!}=(k+1) \frac{N(N+1) \cdots(N+k)}{(k+1)!} $$ Now, we look for a way to simplify the sum and reach the same equation as the first equation. We can start by iterating the sum and evaluating at each step: $$ N\left[\frac{(k-1)!}{(k-1)!(0)!}+\frac{(k)!}{(k-1)!(1)!}+\frac{(k+1)!}{(k-1)!(2)!}+\cdots+\frac{(N+k-1)!}{(k-1)!(N)!}\right]=(k+1) \frac{N(N+1)\cdots(N+k)}{(k+1)!} $$ Notice that the terms of the sum on the left side are related to the binomial coefficients in the first equation. Simplifying the sum, we get: $$ N\frac{(N+k)!}{k!(N!)}=(k+1)\frac{(N+k)!}{(k+1)!(N-1)!} $$ Thus, we've shown that the first equation is equivalent to the second equation.

Proving equivalence of the second and third equations

Now that we've shown the equivalence between the first and second equations, we will focus on the third equation: $$ \sum_{j=1}^{N} \frac{j(j+1) \cdots(j+k-1)}{k !}=\frac{N(N+1) \cdots(N+k)}{(k+1) !} $$ To prove this equivalence, we'll make use of the second equation. We know that: $$ N \sum_{j=k-1}^{N+k-1}\left(\begin{array}{c} j \\\ k-1 \end{array}\right)=(k+1) \frac{N(N+1) \cdots(N+k)}{(k+1) !} $$ Let's change the limits of the sum to be from 1 to N by replacing j with j+k-1 in the sum. This gives us: $$ N \sum_{j=1}^{N}\left(\begin{array}{c} j+k-1 \\\ k-1 \end{array}\right)=(k+1) \frac{N(N+1) \cdots(N+k)}{(k+1) !} $$ Now, we rewrite the third equation in terms of binomial coefficients: $$ \sum_{j=1}^{N} \frac{j(j+1) \cdots(j+k-1)}{k !}=\left(\begin{array}{c} j+k-1 \\\ k-1 \end{array}\right) $$ Comparing the transformed second equation with the transformed third equation, we can see that they are equivalent, once we distribute N inside the sum in the transformed second equation. Therefore, we have shown that Fermat's rule is equivalent to both the second and the third provided equations, completing the proof.

Key concepts

Binomial Coefficients

In mathematics, the binomial coefficients are a family of numbers that appear primarily in combinatorics and algebra in the binomial theorem. They represent the number of ways to choose a subset of items from a larger set. In simpler terms, if you have a set of items and want to choose a specific number of them, without caring about the order, what you're counting is given by a binomial coefficient.

The binomial coefficient is usually denoted by \( \binom{n}{k} \) or \( C(n, k) \) and is read as 'n choose k'. It is defined as the number of ways to pick \( k \) unordered outcomes from \( n \) possibilities, also known as a combination. The formula to calculate it uses factorials, another core concept in this topic, and is given by \( \frac{n!}{k!(n-k)!} \).

For instance, if you're trying to figure out how many different groups of 2 can be made from 4 people, you would calculate the binomial coefficient \( \binom{4}{2} \) which equals 6. This indicates there are 6 potential pairings. It's crucial that the values of \( n \) and \( k \) are non-negative integers and \( k \leq n \) since you can't choose more items than you have.

Combinatorial Notation

Combinatorial notation is a method of expressing common operations in combinatorics in a compact form, allowing for easier manipulation and understanding of combinatorial formulas and concepts. One of the most widely-used combinatorial notations is the aforementioned binomial coefficient notation \( \binom{n}{k} \) which compactly represents combinations.

Another example of combinatorial notation is expressing sums that appear in combinatorial identities, such as \( \sum_{i=1}^{n} \) which denotes the sum of a sequence or series starting at \( i = 1 \) and ending at \( i = n \). This type of notation is especially useful when dealing with proofs and derivations in combinatorics, like in Fermat's rule as demonstrated in the step-by-step solution for the given exercise.

Mastery of combinatorial notation is essential for working through combinatorial problems, as it provides a standard way to understand and communicate the structure of combinatorial arguments and proofs.

Factorial

The factorial, denoted by the exclamation mark (!), is a function that multiplies a series of descending natural numbers and is defined for all non-negative integers. The factorial of a non-negative integer \( n \) is the product of all positive integers less than or equal to \( n \) and is denoted by \( n! \). For example, \( 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \).

The value of 0! is defined as 1, which may seem counterintuitive at first but is important for mathematical consistency, particularly in combinatorial formulas. Factorials are integral in combinatorics because they are used to calculate the number of permutations, or possible orderings, of a set of elements.

Understanding factorials is crucial when dealing with binomial coefficients, as the factorial function is part of the formula for calculating them. When looking at combinatorial problems involving larger numbers, the factorials can grow very quickly, making exact calculations cumbersome. That's why simplifying expressions with factorials, a technique showcased in the Fermat's rule exercise, is a valuable skill in solving combinatorial problems.