Nishu_Coder's blog

Need help in a discrete math concept.
By Nishu_Coder, history, 12 months ago, In English

Guys please don't downvote my blog. I genuinely need the help. My doubt is if I am given a sequence 1,2,4,8,15,26,... Then how to find a closed formula for this series in this case. please help me. I know this is not relevant to cp. But it will genuinely help to understand the mathematical computation regarding solving subproblems.

As far as i have read this involves polynomial fitting. How to solve this by polynomial fitting . please kindly help.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use The On-Line Encyclopedia of Integer Sequences. For your sequence it gives several variants. For example C(n+1,3) + n + 1.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I am familiar with this website. But i really want to develop the skill of finding close formulas using polynomial fitting which comes under discrete mathematics. so if you know this skill please kindly help. It might help me in doing mathematical computation. Afterall having mathematical maturity will be essential in solving subproblems and will certainly help me in future contests.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 4   Vote: I like it -7 Vote: I do not like it

      I have never heard of polynomial fitting before reading this blog. I think it is safe to say this technique is not going to be helpful in CP contests.

      Edit: My bad, I thought polynomial fitting is completely different from polynomial interpolation, which is useful as it is exact. Lagrange interpolation could be a useful technique in your case.

      Resource: https://brilliant.org/wiki/lagrange-interpolation/

      CP blog (keep in mind I haven't read it): https://codeforces.com/blog/entry/82953

      → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 2   Vote: I like it -18 Vote: I do not like it

      Edit: This is wrong

      Polynomial fitting only works when the equation is a polynomial. Most of the time in CP the sequence we want to find polynomial cannot be represented as a polynomial. For example the formula $$$n+1 \choose 3$$$ $$$ + n + 1$$$ that was mentioned above cannot be found with polynomial fitting. More likely than not, trying to use polynomial fitting will result in a false positive that is completely wrong.

      → Reply