3
$\begingroup$

Discrete formulas such as the Faulhaber summations can be verified by evaluating them for a finite number of values.

For example $$\sum_{k=1}^nk=\frac{n(n+1)}2$$ is validated by evaluating for $n=0,1,2$ (indeed $0=0,0+1=2/2,0+1+2=2\cdot3/2$) because both sides are quadratic polynomials.

Can we generalize the approach to other kinds of formulas ? For instance, how many trials for $$\sum_{k=0}^n \binom{n}{k}2^k = 3^n$$

$\endgroup$
12
  • $\begingroup$ How do you show that the LHS of the first formula (Faulhaber summation) is a quadratic function? $\endgroup$
    – PenasRaul
    Commented Oct 24, 2016 at 12:25
  • $\begingroup$ Because the first order finite difference is a linear function (namely $n$). $\endgroup$
    – user65203
    Commented Oct 24, 2016 at 12:26
  • $\begingroup$ So I would say that there is no gain in using this approach, as with that you can almost guess the value of the function. If you are a professor, consider tell your students to guess the value of the function by looking to the fewest possible numbers, assuming that the function belongs to a prescribed set (to me it's not clear what set would belong $\sum \binom{n}{k} 2^k $. If you are a student answer zero and show the equality. $\endgroup$
    – PenasRaul
    Commented Oct 24, 2016 at 12:36
  • $\begingroup$ I should add, there's definitely no "correct" answer here, as $3$ wouldn't be a correct answer in the previous one. By using induction you have only to show that those functions coincide in one value and that the finite differences are identically the same. $\endgroup$
    – PenasRaul
    Commented Oct 24, 2016 at 12:37
  • 1
    $\begingroup$ @DavidK: this is the core of my question. $\endgroup$
    – user65203
    Commented Oct 25, 2016 at 6:21

0

Reset to default

You must log in to answer this question.