When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Nishu_Coder's blog

By Nishu_Coder, history, 10 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

»
10 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.

  • »
    »
    10 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.

    • »
      »
      »
      10 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

    • »
      »
      »
      10 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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so if you know this skill please kindly help

      You know it already: Polynomial Fitting. If you have enough sequence items you can construct first differences sequence, then second differences sequence and so on till you get the sequence with the same numbers (if you couldn't reach such sequence with equal numbers then initially you deal with not polynomial sequence). For your sequence:

      • First diffences: 1, 2, 4, 7, 11
      • Second differences: 1, 2, 3, 4
      • Third differences: 1, 1, 1

      Now you can assume that the initial sequence is generated by some polynomial with degree $$$3$$$:

      $$$P(n) = An^3 + Bn^2 + Cn + D$$$

      You should determine the coefficients $A$, $$$B$$$, $$$C$$$ and $$$D$$$. With zero value for $$$n$$$ you can find offhand that $$$D = 1$$$. Substututes values $$$1, 2, 3$$$ for variable $$$n$$$ you get the following system of equations:

      $$$P(1) = A + B + C + 1 = 2$$$
      $$$P(2) = 8A + 4B + 2C + 1 = 4$$$
      $$$P(3) = 27A + 8B + 3C + 1 = 8$$$

      or

      $$$A = \frac{1}{6}, B = 0, C = \frac{5}{6}$$$

      Now you have the desired formula.