Recurrence relationer of intersection points formed by the diagonals of a convex polygon.

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

Derive a recurrence relation to represent the number of intersection points formed by the diagonals of a convex polygon with n vertices. Show that the solution of the recurrence relation is $binom n4$.

I have derived the recurrence relation but failed to get its solution. The relation is $R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1$.

I tried to use generating function to solve it.

recurrence-relations

share|cite|improve this question

edited Jul 25 at 16:52

Parcly Taxel

33.5k136588

asked Jul 25 at 16:19

Sambasivarao Mukkamala

61

• 
  
  
  

  
  

  
  
  
  
  
  

  
  OK, what have you tried towards solving the problem?
  – Parcly Taxel
  Jul 25 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I have derived the recurrence relation but failed to get its solution. The relation is R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1.
  – Sambasivarao Mukkamala
  Jul 25 at 16:21
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I tried to use generating function to solve it.
  – Sambasivarao Mukkamala
  Jul 25 at 16:37
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

Derive a recurrence relation to represent the number of intersection points formed by the diagonals of a convex polygon with n vertices. Show that the solution of the recurrence relation is $binom n4$.

I have derived the recurrence relation but failed to get its solution. The relation is $R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1$.

I tried to use generating function to solve it.

recurrence-relations

share|cite|improve this question

edited Jul 25 at 16:52

Parcly Taxel

33.5k136588

asked Jul 25 at 16:19

Sambasivarao Mukkamala

61

• 
  
  
  

  
  

  
  
  
  
  
  

  
  OK, what have you tried towards solving the problem?
  – Parcly Taxel
  Jul 25 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I have derived the recurrence relation but failed to get its solution. The relation is R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1.
  – Sambasivarao Mukkamala
  Jul 25 at 16:21
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I tried to use generating function to solve it.
  – Sambasivarao Mukkamala
  Jul 25 at 16:37
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

Derive a recurrence relation to represent the number of intersection points formed by the diagonals of a convex polygon with n vertices. Show that the solution of the recurrence relation is $binom n4$.

I have derived the recurrence relation but failed to get its solution. The relation is $R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1$.

I tried to use generating function to solve it.

recurrence-relations

share|cite|improve this question

edited Jul 25 at 16:52

Parcly Taxel

33.5k136588

asked Jul 25 at 16:19

Sambasivarao Mukkamala

61

Derive a recurrence relation to represent the number of intersection points formed by the diagonals of a convex polygon with n vertices. Show that the solution of the recurrence relation is $binom n4$.

I have derived the recurrence relation but failed to get its solution. The relation is $R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1$.

I tried to use generating function to solve it.

recurrence-relations

share|cite|improve this question

edited Jul 25 at 16:52

Parcly Taxel

33.5k136588

asked Jul 25 at 16:19

Sambasivarao Mukkamala

61

share|cite|improve this question

share|cite|improve this question

edited Jul 25 at 16:52

Parcly Taxel

33.5k136588

edited Jul 25 at 16:52

Parcly Taxel

33.5k136588

edited Jul 25 at 16:52

Parcly Taxel

33.5k136588

33.5k136588

asked Jul 25 at 16:19

Sambasivarao Mukkamala

61

asked Jul 25 at 16:19

Sambasivarao Mukkamala

61

asked Jul 25 at 16:19

Sambasivarao Mukkamala

61

61

• 
  
  
  

  
  

  
  
  
  
  
  

  
  OK, what have you tried towards solving the problem?
  – Parcly Taxel
  Jul 25 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I have derived the recurrence relation but failed to get its solution. The relation is R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1.
  – Sambasivarao Mukkamala
  Jul 25 at 16:21
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I tried to use generating function to solve it.
  – Sambasivarao Mukkamala
  Jul 25 at 16:37
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  OK, what have you tried towards solving the problem?
  – Parcly Taxel
  Jul 25 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I have derived the recurrence relation but failed to get its solution. The relation is R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1.
  – Sambasivarao Mukkamala
  Jul 25 at 16:21
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I tried to use generating function to solve it.
  – Sambasivarao Mukkamala
  Jul 25 at 16:37
  

  
  
  
  

OK, what have you tried towards solving the problem?
– Parcly Taxel
Jul 25 at 16:20

OK, what have you tried towards solving the problem?
– Parcly Taxel
Jul 25 at 16:20

I have derived the recurrence relation but failed to get its solution. The relation is R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1.
– Sambasivarao Mukkamala
Jul 25 at 16:21

I have derived the recurrence relation but failed to get its solution. The relation is R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); R_4 = 1.
– Sambasivarao Mukkamala
Jul 25 at 16:21

I tried to use generating function to solve it.
– Sambasivarao Mukkamala
Jul 25 at 16:37

I tried to use generating function to solve it.
– Sambasivarao Mukkamala
Jul 25 at 16:37

add a comment | 

1 Answer
1

active

oldest

votes

up vote
0
down vote

The relation is $;R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); ;R_4 = 1,$.

First off:

$$
beginalign
sum _k=2^n-1(k-1)(n-k) = sum _k=1^n-2 k(n-k-1) &= (n-1) cdot sum _k=1^n-2k - sum _k=1^n-2 k^2 \
&= (n-1) cdot frac(n-2)(n-1)2 - frac(n-2)(n-1)(2n-3)6 \
&= fracn(n-1)(n-2)6 \
&= binomn3
endalign
$$

(The combinatorial interpretation of this is fairly straightforward: when adding the $,(n+1)^th,$ vertex to the previous $n$-gon, the new intersections of diagonals are precisely those where one of the diagonals originates at the newly added vertex.)

Then, telescoping:

$$
beginalign
R_n &= R_n-1 + binomn-13 \
&= R_n-2 + binomn-23 + binomn-13 \
& cdots \
&= R_4 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binom33 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binomn4
endalign
$$

The last step used the hockey-stick identity $displaystyle binom n+1k+1=sum_j=k^n binomjk,$.

share|cite|improve this answer

edited Jul 25 at 19:44

answered Jul 25 at 19:28

dxiv

53.9k64796

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862575%2frecurrence-relationer-of-intersection-points-formed-by-the-diagonals-of-a-convex%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

The relation is $;R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); ;R_4 = 1,$.

First off:

$$
beginalign
sum _k=2^n-1(k-1)(n-k) = sum _k=1^n-2 k(n-k-1) &= (n-1) cdot sum _k=1^n-2k - sum _k=1^n-2 k^2 \
&= (n-1) cdot frac(n-2)(n-1)2 - frac(n-2)(n-1)(2n-3)6 \
&= fracn(n-1)(n-2)6 \
&= binomn3
endalign
$$

(The combinatorial interpretation of this is fairly straightforward: when adding the $,(n+1)^th,$ vertex to the previous $n$-gon, the new intersections of diagonals are precisely those where one of the diagonals originates at the newly added vertex.)

Then, telescoping:

$$
beginalign
R_n &= R_n-1 + binomn-13 \
&= R_n-2 + binomn-23 + binomn-13 \
& cdots \
&= R_4 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binom33 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binomn4
endalign
$$

The last step used the hockey-stick identity $displaystyle binom n+1k+1=sum_j=k^n binomjk,$.

share|cite|improve this answer

edited Jul 25 at 19:44

answered Jul 25 at 19:28

dxiv

53.9k64796

add a comment | 

up vote
0
down vote

The relation is $;R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); ;R_4 = 1,$.

First off:

$$
beginalign
sum _k=2^n-1(k-1)(n-k) = sum _k=1^n-2 k(n-k-1) &= (n-1) cdot sum _k=1^n-2k - sum _k=1^n-2 k^2 \
&= (n-1) cdot frac(n-2)(n-1)2 - frac(n-2)(n-1)(2n-3)6 \
&= fracn(n-1)(n-2)6 \
&= binomn3
endalign
$$

(The combinatorial interpretation of this is fairly straightforward: when adding the $,(n+1)^th,$ vertex to the previous $n$-gon, the new intersections of diagonals are precisely those where one of the diagonals originates at the newly added vertex.)

Then, telescoping:

$$
beginalign
R_n &= R_n-1 + binomn-13 \
&= R_n-2 + binomn-23 + binomn-13 \
& cdots \
&= R_4 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binom33 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binomn4
endalign
$$

The last step used the hockey-stick identity $displaystyle binom n+1k+1=sum_j=k^n binomjk,$.

share|cite|improve this answer

edited Jul 25 at 19:44

answered Jul 25 at 19:28

dxiv

53.9k64796

add a comment | 

up vote
0
down vote

up vote
0
down vote

The relation is $;R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); ;R_4 = 1,$.

First off:

$$
beginalign
sum _k=2^n-1(k-1)(n-k) = sum _k=1^n-2 k(n-k-1) &= (n-1) cdot sum _k=1^n-2k - sum _k=1^n-2 k^2 \
&= (n-1) cdot frac(n-2)(n-1)2 - frac(n-2)(n-1)(2n-3)6 \
&= fracn(n-1)(n-2)6 \
&= binomn3
endalign
$$

(The combinatorial interpretation of this is fairly straightforward: when adding the $,(n+1)^th,$ vertex to the previous $n$-gon, the new intersections of diagonals are precisely those where one of the diagonals originates at the newly added vertex.)

Then, telescoping:

$$
beginalign
R_n &= R_n-1 + binomn-13 \
&= R_n-2 + binomn-23 + binomn-13 \
& cdots \
&= R_4 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binom33 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binomn4
endalign
$$

The last step used the hockey-stick identity $displaystyle binom n+1k+1=sum_j=k^n binomjk,$.

share|cite|improve this answer

edited Jul 25 at 19:44

answered Jul 25 at 19:28

dxiv

53.9k64796

The relation is $;R_n+1 = R_n+sum _k=2^n-1(k-1)(n-k); ;R_4 = 1,$.

First off:

$$
beginalign
sum _k=2^n-1(k-1)(n-k) = sum _k=1^n-2 k(n-k-1) &= (n-1) cdot sum _k=1^n-2k - sum _k=1^n-2 k^2 \
&= (n-1) cdot frac(n-2)(n-1)2 - frac(n-2)(n-1)(2n-3)6 \
&= fracn(n-1)(n-2)6 \
&= binomn3
endalign
$$

(The combinatorial interpretation of this is fairly straightforward: when adding the $,(n+1)^th,$ vertex to the previous $n$-gon, the new intersections of diagonals are precisely those where one of the diagonals originates at the newly added vertex.)

Then, telescoping:

$$
beginalign
R_n &= R_n-1 + binomn-13 \
&= R_n-2 + binomn-23 + binomn-13 \
& cdots \
&= R_4 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binom33 + binom43+binom53+ldots + binomn-23 + binomn-13 \
&= binomn4
endalign
$$

The last step used the hockey-stick identity $displaystyle binom n+1k+1=sum_j=k^n binomjk,$.

share|cite|improve this answer

edited Jul 25 at 19:44

answered Jul 25 at 19:28

dxiv

53.9k64796

share|cite|improve this answer

share|cite|improve this answer

edited Jul 25 at 19:44

edited Jul 25 at 19:44

edited Jul 25 at 19:44

answered Jul 25 at 19:28

dxiv

53.9k64796

answered Jul 25 at 19:28

dxiv

53.9k64796

answered Jul 25 at 19:28

dxiv

53.9k64796

53.9k64796

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862575%2frecurrence-relationer-of-intersection-points-formed-by-the-diagonals-of-a-convex%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email