Combinatorics and alternating series

In summary, the author is trying to solve a problem where they are not sure how to do the (-1) part of an induction proof. They are looking for help from others and ask if anyone knows how to do this particular part of the proof. Someone suggests using the recursion formula and proves the equation for r+1.
  • #1
QuantumP7
68
0

Homework Statement



Prove that

[tex] 1 - \dbinom{n}{1}\ + \dbinom{n}{2} \ - \dbinom{n}{3} \ + \cdots \ + (-1)^r \dbinom{n}{r} = (-1)^r \dbinom{n - 1}{r} [/tex]

by induction.


Homework Equations





The Attempt at a Solution


Well, I know how to solve the normal binomial sums by using the identity [tex] \dbinom{n}{r} \ = \dbinom{n - 1}{r} \ + \dbinom{n - 1}{r - 1} [/tex]. I'm just not sure what to do with the (-1) part. I can't find any example of an inductive proof using an alternating series anywhere, that does not involve the convergence test. Could anyone give me a hint as to where to go with this problem?
 
Last edited:
Physics news on Phys.org
  • #2
QuantumP7 said:
Prove that

[tex] 1 - \dbinom{n}{1}\ + \dbinom{n}{2} \ - \dbinom{n}{3} \ + \cdots + (-1)^r \ \dbinom{n - 1}{r} [/tex]

by induction.

This statement is incomplete as written.
 
  • #3
I'm SO sorry! I fixed it. Thank you for pointing this out!
 
  • #4
It might make it easier to write the identity as
[tex] (-1)^r \dbinom{n - 1}{r} = \sum_{k=0}^r (-1)^{r-k} \begin{pmatrix} n \\ r-k \end{pmatrix}.[/tex]I'm not sure yet if the recursive formula is any easier than the factorial formula. It might help to use both at some point.
 
  • #5
Well, for n + 1, would the equation be

[tex] 1 - \dbinom{n}{1} + \dbinom{n}{2} \ - \dbinom{n}{3} + \cdots + (-1)^{r - 1 }
\dbinom{n}{r} + (-1)^r \dbinom{n + 1}{r} [/tex] ?
 
  • #6
QuantumP7 said:
Well, for n + 1, would the equation be

[tex] 1 - \dbinom{n}{1} + \dbinom{n}{2} \ - \dbinom{n}{3} + \cdots + (-1)^{r - 1 }
\dbinom{n}{r} + (-1)^r \dbinom{n + 1}{r} [/tex] ?

No, for n+1, just shift [tex]n\rightarrow n+1[/tex] everywhere in the equation in the OP. Induction on n is trivial because you can just multiply through the equation for n by a certain set of factors to show that the (n+1) equation is true. The trickier part is induction on r. It looks like using that series just makes things harder though, so forget that I wrote that and use the recursion formula in the equation for r. You should be able to rearrange things to get the equation for (r+1).
 
  • #7
Oh, I see. Thank you SO much! I wish I could give you some points or something for your help!
 

Related to Combinatorics and alternating series

1. What is combinatorics and how is it related to alternating series?

Combinatorics is a branch of mathematics that deals with counting and arrangements of objects. Alternating series is a type of infinite series that involves adding positive and negative terms in a specific pattern. Combinatorics is used to analyze and solve problems involving alternating series, such as determining if a series converges or diverges.

2. What is the difference between a permutation and a combination in combinatorics?

In combinatorics, a permutation is an arrangement of objects in a specific order, while a combination is a selection of objects without considering the order. For example, the permutations of ABC are ABC, ACB, BAC, BCA, CAB, and CBA, while the combinations are ABC, ACB, BCA. Permutations involve all the objects, while combinations can involve a subset of objects.

3. How is the principle of inclusion-exclusion used in combinatorics?

The principle of inclusion-exclusion is a counting technique used in combinatorics to calculate the number of elements in the union of multiple sets. It states that the sum of the number of elements in each set minus the number of elements in the intersection of all sets gives the total number of elements in the union. This principle is particularly helpful in solving problems involving overlapping elements.

4. What is the formula for an alternating series?

The formula for an alternating series is given by a1 - a2 + a3 - a4 + ... = ∑(-1)n+1an, where a1, a2, a3, ... are the terms of the series and n is the position of the term. This formula can help determine if the series converges or diverges using various tests such as the alternating series test or the ratio test.

5. How is combinatorics used in real-life applications?

Combinatorics has numerous real-life applications, such as in computer science, genetics, economics, and statistics. For example, in computer science, combinatorics is used to analyze algorithms and data structures, while in genetics, it is used to study the possible combinations of genes. In economics, combinatorics is used to analyze various decision-making processes, and in statistics, it is used to calculate probabilities and make predictions.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Math POTW for University Students
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
437
  • Calculus and Beyond Homework Help
Replies
1
Views
504
  • Calculus and Beyond Homework Help
Replies
3
Views
233
  • Calculus and Beyond Homework Help
Replies
2
Views
897
  • Calculus and Beyond Homework Help
Replies
18
Views
5K
  • Precalculus Mathematics Homework Help
Replies
8
Views
1K
Replies
4
Views
2K
Back
Top