The Summation Identity (Combinatorics)

In summary: Summary: In summary, the conversation discusses the use of the Summation Identity to count the cubes of all integer sizes formed by an n by n by n assembly of cubes. The identity is given as "Sum [from i = 0 to n] (i choose k) = (n+1 choose k+1)" and the summation of cubes identity is stated as "Sum [from i = 0 to n] i^3 = (n(n+1)/2)^2". The conversation also contains an attempt at a solution, where k is set to different values and the summation identity is used to simplify the expressions. However, there is a small mistake in the simplification step and the solution is not fully generalized
  • #1
NastyAccident
61
0

Homework Statement


Use the Summation Identity to count the cubes of all integers sizes formed by an n by n by n assembly of cubes.

Homework Equations


Summation Identity:
Sum [from i = 0 to n] (i choose k) = (n+1 choose k+1).

Sum [from i = 0 to n] (i^3) = (n^2)(n+1)^2 / 4 = (sum[from i=0 to n] i)^2 = [(n)(n+1)/2]^2

The Attempt at a Solution



So, let k = 1:
Sum [from i = 0 to n] (i choose 1) = Sum [from i = 0 to n] i = (n+1 choose 2) = n(n+1)/2

So, let k = 2:
Sum [from i = 0 to n] 2!(i choose 2) + (i choose 1) = Sum [from i = 0 to n] i^2 = 2!(n+1 choose 3) + (n+1 choose 2) = n(n+1)/2

So, let k = 3:
Sum [from i = 0 to n] 3! (i choose 3) + 2!(i choose 2) + (i choose 1)...
Unlike before, this does not equal Sum [from i=0 to n] i^3.

I modified this to Sum [from i = 0 to n] 3! (i choose 3) + 3*2!(i choose 2) + (i choose 1) ...
And it now equals Sum [from i=0 to n] i^3.

However, when I use the summation identity on each of the terms I get:
Sum [from i = 0 to n] 3! (i choose 3) + 3*2!(i choose 2) + (i choose 1) = 3! (n+1 choose 4) + 3*2!(n+1 choose 3) + (n+1 choose 2) = 1/4 (n-2) (n-1) n (n+1)+(n-1) n (n+1)+1/2 n (n+1) = 1/4 n^2 (n+1)^2...

Mmm, nevermind. It seems as if I didn't simplify correctly...
Though, still if I could have someone glance over it, I would appreciate it.



NA
 
Physics news on Phys.org
  • #2


Dear NA,

Thank you for sharing your solution and thought process. Overall, your approach seems to be on the right track. However, there are a few points that I would like to clarify and suggest for improvement.

Firstly, in your attempt to use the summation identity for k = 3, you have made a small mistake. The correct expression should be:

Sum [from i = 0 to n] 3! (i choose 3) + 3*2!(i choose 2) + (i choose 1) = 3! (n+1 choose 4) + 3*2!(n+1 choose 3) + (n+1 choose 2) = 1/4 (n+2)(n+1)^2 + 1/2(n+1)^2 + 1/2(n+1) = 1/4(n+1)^2(n+2) + 1/2(n+1)(n+2) + 1/2(n+1) = (n+1)^2(n+2)/4 + (n+1)(n+2)/2 + (n+1)/2 = (n+1)(n+2)(n+3)/4

This simplifies to (n+1)^3, which is the desired result for k = 3. So, it seems like your mistake was in the simplification step.

Secondly, I would suggest using clearer notation for the summation identity. It is commonly written as:

Sum [from i = 0 to n] (i choose k) = (n+1 choose k+1)

And the summation of cubes identity is usually written as:

Sum [from i = 0 to n] i^3 = (n(n+1)/2)^2

Using these notations can make your solution more easily understandable to others.

Lastly, I would recommend trying to generalize your solution for any value of k. This will make your solution more complete and applicable to a wider range of problems.

Overall, you have shown a good understanding of the summation identity and have made a good attempt at using it to solve the problem. Keep up the good work!


 

1. What is the summation identity in combinatorics?

The summation identity in combinatorics is a formula used to calculate the total number of ways to choose a certain number of objects from a larger set without regard to order. It is often represented as nCr, where n represents the total number of objects and r represents the number of objects chosen.

2. How is the summation identity derived?

The summation identity is derived from the fundamental principle of counting in combinatorics. It states that the total number of ways to choose r objects from a set of n objects is equal to n! / (r!(n-r)!), which can also be written as nCr. This formula takes into account the fact that order does not matter in this type of counting.

3. What are some real-world applications of the summation identity?

The summation identity has many applications in various fields, including computer science, statistics, and economics. For example, it can be used to calculate the number of possible combinations of characters in a password, the number of ways to arrange items on a menu, or the number of possible outcomes in a game of chance.

4. Can the summation identity be used for more complex counting problems?

Yes, the summation identity can be extended to solve more complex counting problems that involve multiple sets of objects. This is known as the multinomial coefficient and is represented as nC(r1, r2, ..., rk), where n is the total number of objects and r1, r2, ..., rk represent the number of objects chosen from each set.

5. How does the summation identity relate to other combinatorial identities?

The summation identity is just one of many combinatorial identities, such as the binomial theorem, Pascal's triangle, and the inclusion-exclusion principle. These identities all build upon the fundamental principle of counting and can be used to solve a variety of counting problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
97
  • Calculus and Beyond Homework Help
Replies
5
Views
490
  • Calculus and Beyond Homework Help
Replies
3
Views
356
  • Calculus and Beyond Homework Help
Replies
16
Views
475
  • Calculus and Beyond Homework Help
Replies
7
Views
915
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
1
Views
492
  • Calculus and Beyond Homework Help
Replies
2
Views
695
  • Calculus and Beyond Homework Help
Replies
17
Views
486
Back
Top