MHB Show How to Prove $\binom{n}{r}$ with Pascal's Triangle

  • Thread starter Thread starter JGalway
  • Start date Start date
  • Tags Tags
    Proof
AI Thread Summary
The discussion focuses on proving the identity $\binom{n}{r}=\sum_{i=1}^{r+1}\binom{n-i}{r-i+1}$ using Pascal's Triangle. Participants suggest applying the recursive property of binomial coefficients, $\binom{n}{r}= \binom{n-1}{r}+\binom{n-1}{r-1}$, to derive the result. One user proposes using mathematical induction for a formal proof, while another expresses reluctance towards induction, believing they might be missing a fundamental property of binomial coefficients. The conversation highlights different approaches to the proof, emphasizing the use of Pascal's Triangle and induction. Ultimately, the discussion reveals a preference for direct methods over induction in proving combinatorial identities.
JGalway
Messages
6
Reaction score
0
Repeatedly apply $\binom{n}{r}= \binom{n-1}{r}+\binom{n-1}{r-1}$ to show:

$$\binom{n}{r}=\sum_{i=1}^{r+1}\binom{n-i}{r-i+1}$$

The closest i got was showing you could show different iterations with the binomial coefficients (Pascal's Triangle).
 
Physics news on Phys.org
Hi JGalway,

To prove the result formally, I suggest using the principle of mathematical induction.
 
Euge said:
Hi JGalway,

To prove the result formally, I suggest using the principle of mathematical induction.

Thanks for the reply.
If it's just induction I think I will just ignore it I thought i was missing some property of ${n \choose r}$.(Never really liked induction)
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top