Derivation of the formula for the nth term for a recurrent sequence using the example of the task from the Amnesia quest

Pelengsky farmer Bukh'rik breeds hryaklyuklyuhov. These animals breed so quickly that their livestock increases 3 times daily. But, starting from the second day, a flock of terrible dolbogryz animals began to attack the farm, each evening devouring twice as much hryakoplyukhov than they were on the previous day. How many farms will the farmer have on the 7th evening, if at first there were 10 of them?

You asked the Gaalan what he thinks about this problem. After some reflection, he replied:
- In the beginning there were 10 hryakoplyukhs. On the first day, they multiplied, and by the beginning of the second day they were 30. On the second day, they multiplied again (there were 90), but in the evening dolbogryzy came and ate twice as many hryakoplyukhov than it was yesterday (on the first day), i.e. 20 pieces. Total, at the beginning of the third day we get 70 hryakoplyukhov. It seems to me that, continuing to solve in this way, it is possible to calculate the number of hryakoplyukhov on any given day.

This is a task from the game "Space Rangers 2", quest Amnesia.
Let's try to derive a formula for the number of hryakoplyukhov on the n-th day, and count for example the number of hryakoplyukhov on the 32nd day.

Let's look at the first few days (I added day “0” only for the convenience of the formula, you can do everything without it)

	Day "0"	Day 1	Day 2	Day 3
Morning	0	ten	thirty	70
After breeding	0	10 * 3 = 30	30 * 3 = 90	70 * 3 = 210
After dolbogryzov (evening)	0	10 * 3 - 0 * 2 = 30	30 * 3 - 10 * 2 = 70	70 * 3 - 30 * 2 = 150

We will be interested in the number of hryakoplyukhovs on the morning of the nth day, and, despite the fact that the task asks about the evening, the morning number will be correct.
Thus, the number of hryakoplyukhov (in the morning) is a sequence

$$

$$F = (0, 10, 30, 70, ...)$$

We know about this sequence (by the condition of the problem) that $$$F_0: = 0$and $$$F_1: = 10$
')
Also, according to the condition of the problem, nothing happens at night, so the hryaklyuchs in the evening are transferred without changes to the next morning (i.e. the number of hryakyklyuhs in the morning is equal to their number in the evening of the previous day).

Those. on the morning of the second day they became $$$F_2 = 30 = 3 * 10 - 2 * 0 = 3 * F_1 - 2 * F_0$.
On the morning of the third day they are already $$$F_3 = 70 = 3 * 30 - 2 * 10 = 3 * F_2 - 2 * F_1$.

	Day n-2	Day n-1	Day n
Morning	$$$F_ {n-2}$	$$$F_ {n-1}$	$$$F_ {n} = 3 * F_ {n-1} - 2 * F_ {n-2}$
After breeding	$$$3 * F_ {n-2}$	$$$3 * F_ {n-1}$	$$$3 * F_ {n}$
After dolbogryzov (evening)	$$$3 * F_ {n-2} - 2 * F_ {n-3}$	$$$3 * F_ {n-1} - 2 * F_ {n-2}$	$$$3 * F_ {n} - 2 * F_ {n-1}$

Starting from the second day $$$n = 2$the following recurrence formula works:

$$

$$F_ {n} = 3 * F_ {n-1} - 2 * F_ {n-2}$$

Total, all together again

$$

$$F_0: = 0 \\ F_1: = 10 \\ F_ {n} = 3 * F_ {n-1} - 2 * F_ {n-2}$$

We have obtained a formal definition of the sequence and this is already enough so that we can manually calculate how many hryakoplyukhovs will be on which day. Moreover, if we magically have some formula for $$$F_n$, and this formula is satisfied for these 3 conditions, then this formula will be what we need.

We will try to get this formula.

As a rule, to find something you need to make an equation, so we will do it.
Our sequence $$$F$- this is what we want to find (more precisely, we want to get a formula for its members).

We will make an equation out of sequences. To do this, invent the addition for the sequences:

$$

$$"A + B" = (A_0 + B_0, A_1 + B_1, ....)$$

Those. the sum of the sequences is also a sequence.

It is important to mention that our sequences are actually endless, and so it’s just impossible to do something with them. It is impossible, for example, to sum up all the members of a sequence without any reservations - no one can sit and sum up for an infinite time.

An infinite sequence is where for any member number we can tell how to calculate it in a finite time. In the case of a sequence $$$F$we kind of say: take the day, take the day, and then slowly, step by step, count the following days until you reach the one you need.

For the sum of the sequences, we say: if you need the 100th member of the sum, then take the 100th member from the sum of the sequences and add them. You need the millionth - just take the millionth there, take the millionth here, add these numbers and get what you need.

This is similar to how polynomials sum up, for example:

$$

$$(3 + 2x + x ^ 2) + (6 + 4x ^ 2) = (3 + 6) + (2 + 0) x + (1 + 4) x ^ 2$$

.

You can even imagine an infinite polynomial

$$

$$A = A_0 + A_1 * x + A_2 * x ^ 2 + A_3 * x ^ 3 + ...$$

Where $$$x, x ^ 2, x ^ 3, ..., x ^ n, ...$- just some characters. And if we add two such "infinite members", then their sum will be just the sum of the sequences (this is how we determined the sum of the sequences).

Here it is important to understand that in reality there are no infinite polynomials, it is just a different but more convenient record of an infinite sequence: we write $$$F = 10x + 30x ^ 2 + 70x ^ 3 + ...$and see $$$F = (0, 10, 30, 70, ...)$.

Now we come up with multiplication for sequences. Just pairwise multiply the terms as well as with addition will not go - although it will be like multiplication, it will not give interesting properties. Yes, and I want the multiplication to be similar to the multiplication of polynomials.

For example, ordinary finite polynomials multiply like this:

$$

$$(a_0 + a_1 * x + a_2 * x ^ 2) * (b_0 + b_1 * x + b_2 * x ^ 2) = ???$$

Accepted and multiplied: brackets are revealed, and members with the same degree of xx are grouped

$$

$$(a_0 + a_1 * x + a_2 * x ^ 2) * (b_0 + b_1 * x + b_2 * x ^ 2) = \\ a_0 * (b_0 + b_1 * x + b_2 * x ^ 2) + a_1 * x * (b_0 + b_1 * x + b_2 * x ^ 2) + \\ a_2 * x ^ 2 * (b_0 + b_1 * x + b_2 * x ^ 2) = \\ a_0 * b_0 + \\ x (a_0 * b_1 + a_1 * b_0) + \\ x ^ 2 * \ text {(... something long ...)} + \\ x ^ 3 * \ text {(... something long ...) } + \\ x ^ 4 * \ text {(... something long ...)}$$

In other words, each member of the first polynomial is multiplied by each member of the second.
Each with each.

So simply, it’s impossible to generalize to infinite sequences - again, because no one can multiply an infinite number of times by an infinite number of elements. It is important to say correctly here, namely, that let the n-th member of the product of sequences be

$$

$$"A * B" _n: = A_0 * B_n + A_1 * B_ {n-1} + A_2 * B_ {n-2} + ... + A_n * B_0 = \ sum_ {i = 0} ^ {i = n} A_i * B_ {ni}$$

Now we can add infinite sequences and we can also multiply them. You may notice some good properties, for example, that $$$A + B = B + A$; $$$A * B = B * A$; $$$A * (B + C) = A * B + A * C$. We have invented this addition and multiplication, it is necessary to check that such properties are fulfilled (this is “group” and “ring”). It is easy to check, and, in general, all these properties are quite natural, especially for those who at least somewhat add up and multiply the final polynomials.

Now let's try counting for example. $$$100 * F = (100, 0, 0, 0, .....) * (F_0, F_1, F_2, F_3, ...)$. According to the definition of multiplication we get

$$

$$"100 * F" _n = \ sum_ {i = 0} ^ {i = n} (100, 0, 0, 0, 0, ....) _ i * F_ {ni} = 100 * F_ {n}$$

It looks logical - multiplying a sequence by a number will multiply each term by that number. And it fits with

$$

$$100 * (F_0 + F_1x + F_2x ^ 2 + ...) = 100F_0 + 100F_1x + 100F_2x ^ 2 + ...$$

Important note: $$$1 * F = F * 1 = F$where respectively $$$1 = (1, 0, 0, 0, ....)$

Now calculate $$$x * F = (0, 1, 0, 0, .....) * (F_0, F_1, F_2, F_3, ...)$. Also according to the definition of multiplication we get

$$

$$"x * F" _n = \ sum_ {i = 0} ^ {i = n} (0, 1, 0, 0, 0, ....) _ i * F_ {ni} = F_ {n-1} \ text {for n> 0, or 0 for n = 0}$$

Those.

$$

$$"x * F" = (0, F_0, F_1, F_2, F_3, ...)$$

Which, in fact, also converges with

$$

$$x * (F_0 + F_1x + F_2x ^ 2 + ...) = F_0x + F_1x ^ 2 + F_2x ^ 3 + ...$$

We also get that $$$x ^ 2 * F = (0, 0, F_0, F_1, F_2, ...)$.

These are basic operations on our sequence, and now it would be nice to collect all this and apply it to the initial recurrent formula. $$$F_ {n} - 3 * F_ {n-1} + 2 * F_ {n-2} = 0$:

$$

$$F = (F_0, F_1, F_2, ...) \\ 3 * x * F = (0, 3F_0, 3F_1, 3F_2, ....) \\ 2 * x ^ 2 * F = (0, 0 , 2F_0, 2F_1, 2F_2, ....)$$

From the first line we subtract the second and add the third:

$$

$$F - 3 * x * F + 2 * x ^ 2 * F = \\ (F_0 - 0 + 0, F_1 ​​- 3F_0 + 0, F_2 - 3F_1 + 2F_0, ...., F_ {n} - 3 * F_ {n-1} + 2 * F_ {n-2}) = \\ (F_0, F_1 ​​- 3F_0, 0, 0, 0, ....) = F_0 + (F_1 - 3F_0) x = 10x$$

Total we get (using good properties of addition and multiplication):

$$

$$F * (1 - 3x + 2x ^ 2) = 10x$$

which, I will remind once again, in fact

$$

$$(F_0, F_1, F_2, ....) * (1, -3, 2, 0, 0, ....) = (0, 10, 0, 0, ....)$$

This is the equation, and we will solve it. We can not take it so easy and divide by $$$(1 - 3x + 2x ^ 2)$, if only because we did not define a division operation. Instead, we will multiply both sides of the equation by something that seems to be $$$(1 - 3x + 2x ^ 2) ^ {- 1}$, and ultimately leave the lonely F to the left.
Currently, from what we have, we cannot reliably say whether such a thing exists at all. $$$(1 - 3x + 2x ^ 2) ^ {- 1}$(although this is how it exists, and we will do it now).

Let's slightly transform our equation:

$$

$$F * (1 - 3x + 2x ^ 2) = 10x \\ \ Leftrightarrow \\ F * (1-x) (1/2-x) * 2 = 10x$$

This, again, not just like that, is because the sequence $$$(1, -1, 0, 0, 0, ...)$multiplied by $$$(1/2, -1, 0, 0, 0, ...)$and multiplied by $$$(2, 0, 0, 0, ...)$
gives as a result $$$(1, -3, 2, 0, 0, 0, ...)$
Now it's a little easier, now it would be good to find such$$ $ inline $ "(1-x) ^ {- 1}" $ inline $ and$$ $ inline $ "(1/2-x) ^ {- 1}" $ inline $ , and multiply our equation on them.
There are such reverse sequences, and here is their formula.

$$

$$(\ alpha - x) * (1 / \ alpha + x / \ alpha ^ 2 + x ^ 2 / \ alpha ^ 3 + .... + x ^ {n-1} / \ alpha ^ {n} + ...) = \\ alpha * 1 / \ alpha - x * 1 / \ alpha + \ alpha * x / \ alpha ^ 2 + .... = 1$$

Thus, we multiply both sides of the equation:

$$

$$F * (1-x) (1/2-x) * 2 = 10x \\ \ Leftrightarrow \\ F * (1-x) (1/2-x) * 2 * (1 + x + x ^ 2 + x ^ 3 + ...) * (2 + 4x + 8x ^ 2 + ... + 2 ^ {n + 1} x ^ n + ...) * \\ (1/2) = 10x * ( 1 + x + x ^ 2 + x ^ 3 + ...) * (2 + 4x + 8x ^ 2 + ... + 2 ^ {n + 1} x ^ n + ...) * (1/2 ) \\ \ Leftrightarrow \\ F = 5x * (1 + x + x ^ 2 + x ^ 3 + ...) * (2 + 4x + 8x ^ 2 + ... + 2 ^ {n + 1} x ^ n + ...) \\ \ Leftrightarrow \\ F = 10x * (1 + x + x ^ 2 + x ^ 3 + ...) * (1 + 2x + 4x ^ 2 + ... + 2 ^ {n} x ^ n + ...)$$

Let's take a closer look at

$$

$$(1 + x + x ^ 2 + x ^ 3 + ...) * (1 + 2x + 4x ^ 2 + ... + 2 ^ {n} x ^ n + ...) = \\ (1 , 1, 1, ...., 1, ....) * (1, 2, 4, ...., 2 ^ {n}, ...)$$

By definition of the product, we get the formula for the nth term:

$$

$$"(1, 1, 1, ...., 1, ....) * (1, 2, 4, ...., 2 ^ {n}, ...)" _ {n} = \\ "(1, 2, 4, ...., 2 ^ {n}, ...) * (1, 1, 1, ...., 1, ....)" _ {n} = \\ \ sum_ {i = 0} ^ {i = n} A_i * B_ {ni} = \\ \ sum_ {i = 0} ^ {i = n} 2 ^ {i} = \\ 1 + 2 + 4 + .... + 2 ^ n = 2 ^ {n + 1} - 1$$

Substitute the resulting work

$$

$$F = 10x * (1 + x + x ^ 2 + x ^ 3 + ...) * (1 + 2x + 4x ^ 2 + ... + 2 ^ {n} x ^ n + ...) \ \ \ Leftrightarrow \\ F = 10x * (1, 3, 7, ..., 2 ^ {n + 1} - 1, ...) \\ \ Leftrightarrow \\ F = (0, 10, 30, 70 , ...., 10 * (2 ^ {n} - 1), ...)$$

When multiplied by $$$10x = (0, 10, 0, 0, 0, ...)$all members multiplied by 10 and moved 1 to the right.
Total we get the result

$$

$$F_n = 10 * (2 ^ {n} - 1)$$

It is this formula that should be used to complete the quest, and it can be found in the tips in the quest.
For example, on the 32nd day we get $$$F_ {32} = 10 * (2 ^ {32} - 1) = $ 4294967295$.
Looking at the formula, we can say that dolbogryz hryakuplyuhs are not a hindrance - they, even when eaten, have time to multiply exponentially.

In the same way, you can derive a formula for the nth term of the Fibonacci sequence, although there numbers will be more terrible - with roots, and for any n, the formula will give a natural number.