Introduction

Has it ever happened that you want to sum some infinite series, but you cannot pick up a partial sum of the series? Have you still not used the discrete derivative? Then we go to you!

Definition

Discrete Derivative Sequence $$$a_n$ call this sequence $$$\ Delta a_n$ that for any natural $$$n> 1$ performed:

$$

$$\ Delta a_n = a_n - a_ {n-1}$$

Consider the following examples:

• 
  
  
  
  

  $$

  $$a_n = 1 \\ \ Delta a_n = a_n - a_ {n-1} = 1 - 1 = 0$$
  
  
  
  
  

• 
  
  
  
  

  $$

  $$a_n = n \\ \ Delta a_n = a_n - a_ {n-1} = n - (n - 1) = 1$$
  
  
  
  
  

• 
  
  
  
  

  $$

  $$a_n = n ^ 2 \\ a_n = n ^ 2 - (n - 1) ^ 2 = n ^ 2 - (n ^ 2 - 2n + 1) = 2n-1$$
  
  
  
  
  

• 
  
  
  
  

  $$

  $$a_n = n ^ 3 \\ \ Delta {a_n} = n ^ 3 - (n - 1) ^ 3 = 3n ^ 2 - 3n + 1$$
  
  
  
  
  

• 
  
  
  
  

  $$

  $$a_n = k ^ n \\ \ Delta {a_n} = k ^ n - k ^ {n-1} = k ^ {n-1} (k-1)$$
  
  
  
  
  

Well, you get the point. Something like a derivative of a function, right? We understood how to calculate discrete derivatives of the "simplest" sequences. Ahem, but what about the sum, difference, product, and quotient of sequences? The “ordinary” derivative has some differentiation rules. Let's come up with a discrete one!



First, consider the amount. It is logical that the sum of sequences is also some kind of sequence. Let's try to find the derivative by definition:

$$

$$\ Delta {(a_n + b_n)} = a_n + b_n - (a_ {n - 1} + b_ {n - 1}) = \\ = a_n - a_ {n - 1} + b_n - b_ {n - 1 } = \ Delta {a_n} + \ Delta {b_n}$$

Phenomenally! We have obtained that the derivative of the sum of sequences is the sum of the derivatives of these sequences! thanks, Cap

Let's try to prove the same with the difference

$$

$$\ Delta {(a_n - b_n)} = a_n - b_n - (a_ {n - 1} - b_ {n - 1}) = \\ = a_n - a_ {n - 1} - (b_n - b_ {n - 1}) = \ Delta {a_n} - \ Delta {b_n}$$

And we move on to the work!

Similarly, we find by definition:

$$

$$\ Delta {(a_nb_n)} = a_nb_n - a_ {n-1} b_ {n-1} = \\ = a_nb_n-a_ {n} b_ {n-1} + a_nb_ {n-1} - a_ {n -1} b_ {n-1} = \\ = a_n (b_n - b_ {n-1}) + b_ {n-1} (a_n - a_ {n-1}) = \\ = a_n \ Delta {b_n } + b_ {n-1} \ Delta {a_n}$$

Cool, right? Consider the quotient:

$$

$$\ Delta (\ frac {a_n} {b_n}) = \ frac {a_n} {b_n} - \ frac {a_ {n - 1}} {b_ {n-1}} = \ frac {a_nb_ {n-1 } -a_ {n-1} b_n} {b_nb_ {n-1}} = \\ = \ frac {a_nb_ {n-1} -a_nb_n + a_nb_n-a_ {n-1} b_n} {b_nb_ {n-1 }} = \\ = \ frac {b_n \ Delta {a_n} -a_n \ Delta {b_n}} {b_nb_ {n-1}}$$

Cool ...



But this is all derivative. Maybe there is a discrete antiderivative ? It turns out there is!

More definitions

Discrete primitive sequence $$$a_n$ call such a sequence $$$A_n$ that for any natural $$$n> 1$ performed:

$$

$$a_n = \ Delta A_n$$

• 
  
  
  
  

  $$

  $$a_n = 1 \\ \ Delta A_n = a_n \ iff A_n = n$$
  
  
  
  
  

• 
  
  
  
  

  $$

  $$a_n = n \\ n = \ frac {2n-1} {2} + \ frac {1} {2} = \ frac {\ Delta n ^ 2 + \ Delta n} {2} = \ frac {\ Delta (n ^ 2 + n)} {2} \\ \ Delta A_n = a_n \ iff A_n = \ frac {n ^ 2 + n} {2}$$
  
  
  
  
  

This is understandable. Guo come up with an analogue of Newton-Leibniz!

$$

$$\ sum_ {i = 1} ^ {n} a_i = a_1 + a_2 + a_3 + ... + a_n = \\ = A_1 - A_0 + A_2 - A_1 + ... + A_n - A_ {n-1} = \ \ = A_ {n} - A_0$$

Come on! This joke is a coincidence! And now the same prettier:

$$

$$\ sum_ {i = 1} ^ n a_ = \ sum_ {i = 1} ^ n \ Delta A_i = A_i \ bigg | _ {1} ^ {n}$$

And generalize to the set of natural numbers from $$$a$ before $$$b$ :

$$

$$\ sum_ {i = a} ^ {b} f (i) = F_i \ bigg | _a ^ b$$

Application

Who remembers the very formula for the sum of a series of squares of natural numbers from $$$1$ before $$$n$ ? And here I do not remember. Let's get her out!

But first you need to find the antiderivative for the sequence $$$a_i = i ^ 2$ :

$$

$$i ^ 2 = (3i ^ 2-3i + 1) \ frac {1} {3} + i - \ frac {1} {3} = (3i ^ 2-3i + 1) \ frac {1} {3 } + i - \ frac {1} {3} = \\ = \ frac {1} {3} \ Delta i ^ 3 + \ frac {1} {2} \ Delta (i ^ 2 + i) - \ frac {1} {3} \ Delta i = \\ = \ Delta \ frac {2i ^ 3 + 3i ^ 2 + 3i-2i} {6} = \ Delta \ frac {2i ^ 3 + 3i ^ 2 + i} { 6}$$

And now, in fact, the sum itself:

$$

$$\ sum_ {i = 1} ^ {n} i ^ 2 = \ frac {2i ^ 3 + 3i ^ 2 + i} {6} \ bigg | _0 ^ n = \ frac {2n ^ 3 + 3n ^ 2 + n} {6}$$

What about the sum of the cubes?



First we calculate

$$

$$\ Delta i ^ 4 = i ^ 4 - (i-1) ^ 4 = i ^ 4- (i ^ 4 - 4 i ^ 3 + 6i ^ 2-4i + 1) = 4i ^ 3 - 6i ^ 2 + 4i-1$$

Antiderivative for $$$i ^ 3$ :

$$

$$i ^ 3 = \ frac {1} {4} (4i ^ 3-6i ^ 2 + 4i-1) + \ frac {3} {2} i ^ 2-i + \ frac {1} {4} = \ \ = \ frac {\ Delta i ^ 4} {4} + \ frac {3} {2} \ Delta {\ frac {2i ^ 3 + 3i ^ 2 + i} {6}} - \ Delta {\ frac { i ^ 2 + i} {2}} + \ frac {\ Delta {i}} {4} = \\ = \ Delta {\ frac {i ^ 4 + 2i ^ 3 + 3i ^ 2 + i-2i ^ 2 -2i + i} {4}} = \ Delta {\ frac {i ^ 4 + 2i ^ 3 + i ^ 2} {4}} = \\ = \ Delta {\ bigg (\ frac {i (i + 1 )} {2} \ bigg) ^ 2} \\ \ sum_ {i = 1} ^ {n} i ^ 3 = \ bigg (\ frac {i (i + 1)} {2} \ bigg) ^ 2 \ bigg | _0 ^ n = \ bigg (\ frac {n (n + 1)} {2} \ bigg) ^ 2$$

Ahem, it would seem, nothing complicated ...

For advanced

Finding the integral is not always so easy, right? What do we do in difficult cases? That's right, integrate in parts. Perhaps there is an analogue? I will not torment you, he is, and now we will get him out.



Suppose we need to calculate the sum of a series

$$

$$p = const \\\ sum_ {i = 1} ^ {n} ip ^ {i} =?$$

What to do? It is unlikely that you will be able to so easily pick up the discrete antiderivative to the sequence. Let's watch.



We already know that:

$$

$$\ Delta {(f (n) g (n))} = f (n) \ Delta {g (n)} + g (n-1) \ Delta f (n)$$

Then

$$

$$\ sum_ {i = a} ^ {b} \ Delta (f (i) g (i)) = \ sum_ {i = a} ^ bf (i) \ Delta g (i) + \ sum_ {i = a } ^ {b} g (i-1) \ Delta f (i) \ iff \\ \ iff \ sum_ {i = a} ^ bf (i) \ Delta g (i) = \ sum_ {i = a} ^ {b} \ Delta (f (i) g (i)) - \ sum_ {i = a} ^ {b} g (i-1) \ Delta f (i)$$

And now one nontrivial step:

$$

$$\ sum_ {i = a} ^ {b} \ Delta (f (i) g (i)) = f (a) g (a) -f (a-1) g (a-1) + f (a +1) g (a + 1) - f (a) g (a) + \\ + ... + f (b) g (b) -f (b-1) g (b-1) = f ( b) g (b) -f (a-1) g (a-1)$$

Substitute the equality obtained before:

$$

$$\ sum_ {i = a} ^ bf (i) \ Delta g (i) = f (b) g (b) -f (a-1) g (a-1) - \ sum_ {i = a} ^ {b} g (i-1) \ Delta f (i)$$

Finita la comedy.



Find the same amount:

$$

$$\ sum_ {i = 1} ^ n {ip ^ {i}} = S_n \\ p ^ i = \ Delta {\ frac {p ^ {i + 1}} {p-1}} \\ S_n = \ sum_ {i = 1} ^ ni \ Delta {\ frac {p ^ {i + 1}} {p-1}} \\ $$

It may seem to someone that the formula has become even more cumbersome, and we only complicated our work. But this is not so. Let be $$$f (i) = i, g (i) = \ frac {p ^ {i + 1}} {p-1}$ then:

$$

$$\ sum_ {i = 1} ^ nf (i) \ Delta g (i) = f (n) g (n) -f (0) g (0) - \ sum_ {i = 1} ^ {n} g (i-1) \ Delta f (i) = \\ = n \ frac {p ^ {n + 1}} {p-1} - 0 - \ sum_ {i = 1} ^ {n} \ frac {p ^ {i}} {p-1} = n \ frac {p ^ {n + 1}} {p-1} - \ bigg (\ frac {1} {p-1} \ sum_ {i = 1} ^ {n} p ^ i \ bigg) = \\ = n \ frac {p ^ {n + 1}} {p-1} - \ bigg (\ frac {1} {p-1} \ sum_ {i = 1 } ^ {n} \ Delta {\ frac {p ^ {i + 1}} {p-1}} \ bigg) = \\ = n \ frac {p ^ {n + 1}} {p-1} - \ bigg (\ frac {p ^ {n + 1} -p} {(p-1) ^ 2} \ bigg) = \ frac {np ^ {n + 2} - (n + 1) p ^ {n + 1} + p} {(p-1) ^ 2}$$

Cool puzzle

I propose to practice with this on the example of a problem from the selection in Tinkoff Generation for courses on Machine Learning . Here is the problem itself:



You are tired of solving problems from the selections to Tinkoff Generation courses and decided to take a break by watching several episodes of the new series that everyone is talking about.



You start to watch all the series, starting with the first. Each episode lasts one hour. After watching the next series, you with constant probability ppp start watching the next one, otherwise your break will end and you will return to work.



Starvation, sleep, and other needs do not stop you, and the series has an infinite number of episodes; in theory, your break can last forever.



How long will your average break last?



Strictly speaking, here we need to find the mathematical expectation. Let's get it right.

Decision

The probability that the break will last 1 hour is:

$$

$$P (1) = 1 - p$$

2 hours

$$

$$P (2) = p (1-p) \\ ...$$

n hours:

$$

$$P (n) = p ^ {n-1} (1-p)$$

Then the expectation is:

$$

$$E [X] = \ lim \ limits_ {n \ to \ infty} {\ sum_ {i = 1} ^ ni * P (i)} = \ lim \ limits_ {n \ to \ infty} {\ sum_ {i = 1} ^ ni * (1-p) p ^ {i-1}} = \\ = (1-p) \ lim \ limits_ {n \ to \ infty} {\ sum_ {i = 1} ^ ni * p ^ {i-1}}$$

It’s familiar, right?



We already found that

$$

$$\ sum_ {i = 1} ^ nip ^ {i} = \ frac {np ^ {n + 2} - (n + 1) p ^ {n + 1} + p} {(p-1) ^ 2}$$

then the row we need is quite obvious:

$$

$$\ sum_ {i = 1} ^ nip ^ {i-1} = \ frac {1} {p} \ sum_ {i = 1} ^ nip ^ {i} = \ frac {np ^ {n + 1} - (n + 1) p ^ n + 1} {(p-1) ^ 2}$$

And the task comes down to finding the limit of sequence

$$

$$\ lim \ limits_ {n \ to \ infty} \ frac {np ^ {n + 1} - (n + 1) p ^ n + 1} {(p-1) ^ 2}$$

Where $$$p <1$ , as $$$p$ - probability of the event.

We prove now that

$$

$$\ lim \ limits_ {n \ to \ infty} np ^ {n + 1} = 0, \ space \ lim \ limits_ {n \ to \ infty} p ^ n (n + 1) = 0$$

• 
  
  
  
  

  $$

  $$f (x) = p ^ {x + 1} x, \ space x \ in \! R \\ p = \ frac {1} {q}, \ space 0 <p <1 \ iff q> 1 \\ \ lim \ limits_ {x \ to \ infty} {f (x)} = \ lim \ limits_ {x \ to \ infty} {p ^ {x + 1} x} = \ lim \ limits_ {x \ to \ infty } {\ frac {x} {q ^ {x + 1}}} = \\ = \ lim \ limits_ {x \ to \ infty} {\ frac {x '} {(q ^ {x + 1})' }} = \ lim \ limits_ {x \ to \ infty} {\ frac {1} {q ^ {x + 1} \ ln q}} = 0 \\ \ lim \ limits_ {x \ to \ infty} f ( x) = 0 \ implies \ lim \ limits_ {n \ to \ infty} f (n) \ iff \ lim \ limits_ {n \ to \ infty} np ^ {n + 1} = 0$$
  
  
  
  
  
  
  

• 
  
  
  
  

  $$

  $$f (x) = p ^ {x} (x + 1), \ space x \ in \! R \\ p = \ frac {1} {q}, \ space 0 <p <1 \ iff q> 1 \\ \ lim \ limits_ {x \ to \ infty} {f (x)} = \ lim \ limits_ {x \ to \ infty} {p ^ {x} (x + 1)} = \ lim \ limits_ {x \ to \ infty} {\ frac {x + 1} {q ^ {x}}} = \\ = \ lim \ limits_ {x \ to \ infty} {\ frac {(x + 1) '} {(q ^ {x}) '}} = \ lim \ limits_ {x \ to \ infty} {\ frac {1} {q ^ {x} \ ln q}} = 0 \\ \ lim \ limits_ {x \ to \ infty} f (x) = 0 \ implies \ lim \ limits_ {n \ to \ infty} f (n) \ iff \ lim \ limits_ {n \ to \ infty} (n + 1) p ^ {n} = 0$$
  
  
  
  
  
  
  

Now it’s easy to understand that

$$

$$\ lim \ limits_ {n \ to \ infty} \ frac {np ^ {n + 1} - (n + 1) p ^ n + 1} {(p-1) ^ 2} = \ frac {1} { (p-1) ^ 2}$$

AND

$$

$$E [X] = (1-p) \ lim \ limits_ {n \ to \ infty} \ sum_ {i = 1} ^ n {ip ^ {i-1}} = (1-p) \ frac {1 } {(p-1) ^ 2} = \ frac {1} {1-p}$$

Some up

Fuh ... It was easy-peasy tough, even for me, dear readers. List of achievements for today:

1. We understood what a discrete derivative is.
2. Derived the inherent rules of differentiation
3. We understood what a discrete antiderivative is.
4. We derived an analogue of the Newton-Leibniz formula
5. Derived an analog of integration by parts
6. We solved the difficult task of selecting ML courses at Tinkoff Generation

Not bad for a start, what do you think?



Waiting for your comments in the comments, the kites are the most attentive!