Prove Pascal's Triangle-type Function - Discrete Mathematics

  • Thread starter yellowsnow
  • Start date
  • #1
yellowsnow
4
0

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,216
22
That's pascal's triangle, but that also has a lot to do with the binomial theorem. Try using that.
 

Suggested for: Prove Pascal's Triangle-type Function - Discrete Mathematics

Replies
23
Views
510
Replies
8
Views
264
Replies
12
Views
601
Replies
5
Views
329
Replies
20
Views
826
Replies
8
Views
553
Replies
12
Views
370
Replies
8
Views
558
Replies
35
Views
3K
Top