sum of the first m terms of n^3/2^n = ?

[zerocordas]

according to the source* , this expression f(m) is a fact one "notices" in order to get the value for m infinite ...... which is 26 !

 

 

* les math au carré , by Marie-France Palissard

[mathematic]

The expression (n^3/2^n) is confusing. Use parentheses to clarify.

[zerocordas]

oh sure ! (n^3)/(2^n)

 

n^3 a classic 2^n not to mention but combined ?

[renerpho]

First step: Use induction to show that the partial sum equals [math]\sum_{n=1}^{m}\frac{n^3}{2^n} = 26-\frac {m^3+6m^2+18m+26}{2^m}[/math].

Second step: [math]\lim_{m\to\infty} 26-\frac {m^3+6m^2+18m+26}{2^m} = 26 - \lim_{m\to\infty} \frac {m^3}{2^m} - \lim_{m\to\infty} \frac {6m^2}{2^m} - \lim_{m\to\infty} \frac {18m}{2^m} - \lim_{m\to\infty} \frac {26}{2^m} = 26[/math]

[zerocordas]

sure but what if you were asked to derive f(m) from scratch ?

[renerpho]

If you want to keep the proof elementar, you will have to put some ideas into it. Here is one possible approach:

Notice that your sum is of the form [math]\sum_{n=1}^{m}\frac{P(n)}{2^n}[/math] where [math]P[/math] is a polynomial. You start your proof with an educated guess, that the sum will be of similar form, namely [math]\sum_{n=1}^{m}\frac{n^3}{2^n}\stackrel{?!}{=}\frac{{Q{_1}(m)}2^m+Q{_2}(m)}{2^m}[/math] where [math]Q{_1}[/math] and [math]Q{_2}[/math] are themselves polynomials (you include a polynomial term multiplied by [math]2^m[/math] to increase your chances of success). There is no guarantee that this will succeed, but it's a starting point. So you make trial&error.

You can be quite confident that [math]Q{_2}[/math] will be of at least same degree as [math]P[/math] (sums and integrals don't tend to decrease the degree of polynomials involved). So, your first attempt is the simplest possible, where [math]Q{_1}[/math] has degree 0 (turning it into a constant, possibly 0) and [math]Q{_2}[/math] has degree 3.

This leads you to [math]\sum_{n=1}^{m}\frac{n^3}{2^n}\stackrel{?!}{=}\frac{{a}2^m+{b}m^3+{c}m^2+{d}m+e}{2^m}[/math] for some real numbers [math]a,b,c,d,e[/math].

Evaluate at [math]m=1,\dots,5[/math] and you get a system of 5 linear equations in 5 variables. That means that IF your guess was correct then this will lead you to the only possible solution. That's the one presented in my previous post, and once you found it you can proof it by induction.

And indeed, you will find that [math]\begin{pmatrix}2 & 1 & 1 & 1 & 1 \\ 4 & 8 & 4 & 2 & 1 \\ 8 & 27 & 9 & 3 & 1 \\ 16 & 64 & 16 & 4 & 1 \\ 32 & 125 & 25 & 5 & 1\end{pmatrix}\begin{pmatrix}a \\ b \\ c \\ d \\ e\end{pmatrix}=\begin{pmatrix}1 \\ 10 \\ 47 \\ 158 \\ 441\end{pmatrix}[/math] , with the unique solution [math]\begin{pmatrix}a \\ b \\ c \\ d \\ e\end{pmatrix}=\begin{pmatrix}26 \\ -1 \\ -6 \\ -18 \\ -26\end{pmatrix}[/math] immediately resulting in the formula shown to be correct earlier.

 

Notice that you still have to prove it by induction, because so far this only shows that the claim is correct for [math]m=1,\dots,5[/math].

 

The very same trick will work for many summation formula that are usually proved by induction.

Edited September 29, 2016 by renerpho

[renerpho]

(1) An idea to reduce the amount of guesswork in my previous ansatz:

Because the infinite sum converges (this is easy to show), [math]Q{_1}(m)[/math] has to be a constant, and it will be equal to the value of the infinite sum. That's because [math]\lim_{m\to\infty} \frac{{Q{_1}(m)}2^m+Q{_2}(m)}{2^m} = \lim_{m\to\infty} {Q{_1}(m)}[/math], and as [math]Q[/math] is a polynomial this limit only exists if [math]Q[/math] is constant and is equal to the value of the infinite sum. If you already suspect the infinite sum to be equal to 26 then you can save some work by setting [math]a=26[/math], reducing the number of linear equations to 4.

 

 

(2) Here is an alternative ansatz that avoids induction (for the cost of being less elementar). But it is more powerful because it can solve an infinite class of similar problems, and more elegant because there's no need for any "guesswork".

Let [math](p,q)[/math] be a pair of real numbers, with [math]q>1[/math]. Notice that [math]\sum_{n=1}^{\infty }\frac{n^p}{q^n}=\sum_{n=1}^{\infty }{\frac{(1/q)^n}{n^{-p}}}[/math]. Because of [math]q>1[/math] that sum converges. We are going to evaluate it by turning the problem into one about power series; the series involved is the one that defines the polylogarithm [math]\textup{Li}_{s}(x)[/math].

Definition: [math]\textup{Li}_{s}(x):= \sum_{n=1}^{\infty }\frac{x^n}{n^s}=x+\frac{x^2}{2^s}+\frac{x^3}{3^s}+\dots[/math]

With that, we get [math]\sum_{n=1}^{\infty }\frac{n^p}{q^n}=\textup{Li}_{-p}\left (1/q \right )[/math]. Set [math]\left ( p,q \right )=\left ( 3,2 \right )[/math] and we get the expression [math]\sum_{n=1}^{\infty }\frac{n^3}{2^n}=\textup{Li}_{-3}(1/2)[/math]. Even though the polylogarithm can not be expressed in terms of elementary functions in the general case, it can be shown to be a rational function if [math]s[/math] is a nonpositive integer, for example [math]\textup{Li}_{-3}(x)=\frac{x(1+4x+x^2)}{(1-x)^4}[/math]. This can be derived via the expression [math]\textup{Li}_{-n}(x)={x^n}\frac{\mathrm{d}^n }{\mathrm{d}x^n} \left (\frac{x}{1-x} \right )[/math] for [math]n=0,1,2, \dots[/math] which itself follows directly (by induction over [math]n[/math]) by simultaneously differentiating [math]n[/math] times both sides of the equation [math]\frac{x}{1-x}=\textup{Li}_{0}(x)[/math] (the well known Taylor formula for [math]\frac{x}{1-x}[/math]).

All this leads to [math]\textup{Li}_{-3}(1/2)=26[/math], giving the searched value.
With the same method, you can show results like [math]\sum_{n=1}^{\infty }\frac{n^2}{2^n}=6[/math], [math]\sum_{n=1}^{\infty }\frac{n^4}{2^n}=150[/math] or [math]\sum_{n=1}^{\infty }\frac{n^5}{4^n}=\frac{4108}{243} \approx 16.905 \dots[/math]

All of these can be shown by the induction method, too - but the computations involved become extremely ugly very, very fast. The formula [math]\sum_{n=1}^{\infty }\frac{n^p}{q^n}={x^p}\frac{\mathrm{d}^p }{\mathrm{d}x^p} \left. \left (\frac{x}{1-x} \right ) \right | _{x=1/q}[/math] for [math]p=0,1,2, \dots[/math] is much easier to evaluate.

Edited October 2, 2016 by renerpho

[zerocordas]

fantastic ! impressive . huge THANK