Prove Pascal's Triangle-type Function - Discrete Mathematics

  • Thread starter yellowsnow
  • Start date
  • #1

Homework Statement



For all nZ+, the function Pn of i variables is defined recursively as follows:
Pn(x1,...,xn) = Pn-1(x1 + x2, x2 + x3,...,xn-1 + xn) and P1(x1) = x1.
Find a closed formula for Pn.

Homework Equations



Pn(x1,...,xn) = Pn-1(x1 + x2, x2 + x3,...,xn-1 + xn) and P1(x1) = x1.

The Attempt at a Solution



So far, I've found it definitely follows a Pascal's Triangle-esque pattern:

P1(x1) = x1
P2(x1,x2) = P1(x1 + x2) = x1 + x2
P3(x1,x2,x3) = P2(x1 + x2, x2 + x3) = P1(x1 + 2x2 + x3) = x1 + 2x2 + x3
P4(x1,x2,x3,x4) = P3(x1 + x2, x2 + x3, x3 + x4) = P2(x1 + 2x2 + x3, x2 + 2x3 + x4) = P1(x1 + 3x2 + 3x3 + x4) = x1 + 3x2 + 3x3 + x4

I know it's very similar to Pascal's triangle, but I'm just not sure how to find a closed form for it.

I'd appreciate any help; thanks!
 

Answers and Replies

  • #2
Char. Limit
Gold Member
1,204
14
That's pascal's triangle, but that also has a lot to do with the binomial theorem. Try using that.
 

Related Threads on Prove Pascal's Triangle-type Function - Discrete Mathematics

Replies
2
Views
1K
Replies
21
Views
5K
Replies
3
Views
2K
  • Last Post
Replies
1
Views
946
Replies
1
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
3
Views
3K
Top