A community for students.
Here's the question you clicked on:
 0 viewing
amoodarya
 one year ago
What strategies are typically used to solve these recurrences?
amoodarya
 one year ago
What strategies are typically used to solve these recurrences?

This Question is Closed

amoodarya
 one year ago
Best ResponseYou've already chosen the best response.0\[f(0)=1\\f(1)=1\\f(n)=\sum_{i=1}^{n}f(i1)f(ni)\\\]

amoodarya
 one year ago
Best ResponseYou've already chosen the best response.0close form of answer is \[\frac{ (2n)! }{n!(n+1)! }\] but I would like to know how to arrive at this solution

campbell_st
 one year ago
Best ResponseYou've already chosen the best response.0what about guess and check

amoodarya
 one year ago
Best ResponseYou've already chosen the best response.0it is too complicated for check and : I do not want to use " induction "

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0The symmetry of the summation is a bit suggestive. For even \(n\), \[\large\sum_{i=1}^nf(i1)f(ni)=2\sum_{i=1}^\frac{n}{2}f(i1)f(ni)\] while for odd \(n\), \[\large\sum_{i=1}^nf(i1)f(ni)=2\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}f(i1)f(ni)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)^2\]

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Suggestive of what though, not sure yet :P

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Some rewriting of the closed form: \[\frac{(2n)!}{n!(n+1)!}=\frac{1}{n+1}\frac{(2n)!}{n!n!}=\frac{1}{n+1}\binom{2n}n\] which is the closed form for the sequence of Catalan numbers: https://en.wikipedia.org/wiki/Catalan_number

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.0Goddammit, I knew I'd seen that closed form before.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Admittedly, we're working backwards here so it's not much help, but there's at least one proof on the wiki page.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.