Combinatorics - Mathematical Induction?

In summary, the conversation discusses a problem involving two summations in discrete math/combinatorics and asks for help in proving it. The textbook used is "Discrete And Combinatorial Mathematics: An Applied Introduction" by Ralph P. Grimaldi, 5th Edition. The conversation also mentions the need to show the relationship between the two summations (∑i³ and ∑i) and how to write it in the proof. It is clarified that the question belongs in the mathematics forum, not computer science.
  • #1
nintendo424
3
0
Hello, I am having trouble solving this problem. Maybe I'm just overreacting to it. In my two semesters in discrete math/combinatorics, I've never seen a problem like this (with two summations) and been asked to prove it. Can some one help?

[itex]\sum^{n}_{i=1} i^3 = \frac{n^2(n+1)^2}{4} = (\sum^{n}_{i=1} i)^2[/itex]

I mean, I know the whole S(n), S(1), S(k), S(k+1) steps, but I'm just unsure of how to write it. The solutions manual for the book skip that problem.

Book: Discrete And Combinatorial Mathematics: An Applied Introduction by Ralph P. Grimaldi, 5th Edition.
 
Physics news on Phys.org
  • #2
First of all, this is a textbook problem, so it belongs in the homework forums. I moved it for you :smile:

Second, you actually need to show two things:

[tex]\sum_{i=1}^n i^3=\frac{n^2(n+1)^2}{4}[/tex]

and

[tex]\sum_{i=1}^n i = \frac{n(n+1)}{2}[/tex]

(and square both sides)

Can you do that?
 
  • #3
Thank you very much! That helped a lot, I just finished my proof. :D That makes sense why you'd have to break it up. I didn't put the relationship between [itex]\sum^{n}_{i=1}i = \frac{n(n+1)}{2}[/itex] and [itex](\sum^{n}_{i=1}i)^2 = \frac{n^2(n+1)^2}{4}[/itex] together. lol
 
  • #4
nintendo424 said:
Hello, I am having trouble solving this problem. Maybe I'm just overreacting to it. In my two semesters in discrete math/combinatorics, I've never seen a problem like this (with two summations) and been asked to prove it. Can some one help?

[itex]\sum^{n}_{i=1} i^3 = \frac{n^2(n+1)^2}{4} = (\sum^{n}_{i=1} i)^2[/itex]

I mean, I know the whole S(n), S(1), S(k), S(k+1) steps, but I'm just unsure of how to write it. The solutions manual for the book skip that problem.

Book: Discrete And Combinatorial Mathematics: An Applied Introduction by Ralph P. Grimaldi, 5th Edition.

These are two separate problems. ∑i³ is one and ∑i is the other. Have you tried either?

The question belongs in mathematics, not computer science.
 
Last edited:

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and arranging objects or elements in a systematic way. It involves studying the different ways in which objects can be combined, arranged, or chosen, and the properties and patterns that arise from these combinations.

2. What is mathematical induction?

Mathematical induction is a proof technique used to prove mathematical statements that are dependent on an integer parameter, such as n. It involves proving that the statement is true for a base case, usually when n=1, and then showing that if the statement is true for n=k, it must also be true for n=k+1.

3. How is mathematical induction used in combinatorics?

In combinatorics, mathematical induction is used to prove theorems and formulas related to counting and arranging objects. It allows us to prove that a statement is true for all values of n, rather than having to check each individual case separately.

4. What are the steps of a mathematical induction proof?

The steps of a mathematical induction proof are:
1. Prove the base case, usually when n=1.
2. Assume that the statement is true for n=k.
3. Use this assumption to prove that the statement is true for n=k+1.
4. Conclude that the statement is true for all values of n by mathematical induction.

5. Can mathematical induction be used to prove all statements?

No, mathematical induction can only be used to prove statements that are dependent on an integer parameter, such as n. It cannot be used to prove statements that are not related to integers, such as inequalities or continuous functions.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
870
  • Calculus and Beyond Homework Help
Replies
4
Views
988
  • Calculus and Beyond Homework Help
Replies
7
Views
339
  • Calculus and Beyond Homework Help
Replies
6
Views
983
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
457
  • Calculus and Beyond Homework Help
Replies
1
Views
450
  • Calculus and Beyond Homework Help
Replies
5
Views
490
Back
Top