1

I am only recently studying how to write proofs, and as an exercise I set off to prove the following equation: \begin{equation} \sum_{j = b}^a\frac{j!}{b!(j-b)!} = \frac{(a+1)!}{(b+1)!(a-b)!} \end{equation}

The strategy I chose for proving this is induction. I performed induction on $\boldsymbol{a}$ —the upper limit of the summation— while considering an arbitrary non-negative integer $\boldsymbol{b}$ as the lower limit of the summation. The base case is $a = b$, which is very trivial to verify, and then I performed the inductive step as follows.

Inductive hypothesis: $\boldsymbol{\sum_{j = b}^{a - 1}\frac{j!}{b!(j-b)!} = \frac{a!}{(b+1)!(a-1-b)!}}$

Inductive step:

\begin{align} \sum_{j = b}^a\frac{j!}{b!(j-b)!} &= \sum_{j = b}^{a - 1}\bigg(\frac{j!}{b!(j-b)!}\bigg) + \frac{a!}{b!(a-b)!} \\ \\ &= \frac{a!}{(b+1)!(a-1-b)!} + \frac{a!}{b!(a-b)!} \\ \\ &= \frac{a!(a-b)}{(b+1)b!(a-b)!} + \frac{a!}{b!(a-b)!} \\ \\ &= \frac{a!}{b!(a-b)!}\bigg(\frac{a-b}{b+1} + 1\bigg) \\ \\ &= \frac{a!}{b!(a-b)!}\bigg(\frac{a+1}{b+1}\bigg) \\ \\ &= \frac{(a+1)!}{(b+1)!(a-b)!} \end{align}

 

Here's my question: does this already conclude the demonstration, or is it necessary to do an analogous procedure with $\boldsymbol{b}$ —that is, consider $\boldsymbol{a}$ to be fixed on some arbitrary value and then perform induction on $\boldsymbol{b}$—?

Werther
  • 85

1 Answers1

1

You do not need to perform induction on b.

Christa Wolf
  • 163
  • 1
    As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Community Oct 13 '21 at 18:05