Set method

While reading the book “Specific Mathematics” , at the same time gaining knowledge and realizing my incompetence in the question, in the very first chapter I came across the method of sets that the authors use to solve the Problem of Josephus . They do not explain the method, considering it too elementary, so I had to look for information about it myself. I didn’t find a detailed description in the Russian-speaking segment of the Internet, so I used the answer from math.stackexchange.com , which I translated later, and now I present it to you so that those who do not understand the method instinctively can also penetrate.
Further - translation from the first person.

Note : in the beginning I will try to describe several key ideas of the repetition method using a (very) simple example. This should give us some basic understanding of this method. But in order to understand what is really going on , we will also consider one much more complicated example ( comment re.: You can find it in the original article, here is just a basic explanation ).

Method of repetition (basic concepts)

This method is based on two main ingredients . The first is the ability to build a linear combination of already known recurrences.
Suppose there is recurrence for $$$x_n$

$$

$$\ begin {align *} {x_0} & = {a_0} \\ {x_n} & = {a_n} + {x_ {n-1}}, \ quad n> 0 \ end {align *}$$

and we have a second recurrence for $$$y_n$

$$

$$\ begin {align *} {y_0} & = {b_0} \\ {y_n} & = {b_n} + {y_ {n-1}}, \ quad n> 0 \ end {align *}$$

In this case, provided that the recurrence data is known, we also know by linearity that the equation with the term added is

$$

$${\ alpha a_n} + {\ beta b_n}$$

will have a result

$$

$${\ alpha x_n} + {\ beta y_n}$$

To show it clearly, let's say $$${a_n} = 3$and $$${b_n} = {5n ^ 2} + {1}$. Assuming we know the results $$${x_n}$and $$${y_n}$recurrence

$$

$$\ begin {align *} {x_0} & = {3} & {y_0} & = {1} \\ {x_n} & = {3} + {x_ {n-1}}, \ quad n> 0 & {y_n} & = {5n ^ 2} + {1} + {y_ {n-1}}, \ quad n> 0 \ end {align *}$$

we also know from linearity that the result of recurrence

$$

$$\ begin {align *} {z_0} & = {7} \\ {z_n} & = {2n ^ 2} + {7} + {z_ {n-1}} \ end {align *}$$

equals

$$

$$\ begin {align *} {z_n} = \ frac {11} {5} {x_n} + \ frac {2} {5} {y_n} \ end {align *}$$

It can be seen that in this case we have a set of two solutions $$${x_n}$and $$${y_n}$which we can linearly combine to find the desired solution $$${z_n}$.
')
BUT: we usually start with recurrence. $$${z_n}$not having suitable candidates available. And this is the second ingredient. We have to build a set.

The second ingredient is building a kit , which can be used for linear combinations. Let's say we start with recurrence

$$

$$\ begin {align *} {z_0} & = {7} \\ {z_n} & = {2n ^ 2} + {7} + {z_ {n-1}}, \ quad {n}> 0 \ tag {1} \ end {align *}$$

If we try to solve this recurrence using the set method, then first we need to generalize the recurrence and use instead

$$

$$\ begin {align *} {\ mathcal {Z} _0} & = {a_0} \\ {\ mathcal {Z} _n} & = {a_n} + {\ mathcal {Z} _ {n-1}}, \ quad {n}> 0 \ end {align *}$$

It's time for some creative ideas, which is usually the most difficult part in using this method. We want to find a set of two members. One of them with $$${a_n} = const$and the other with $$${a_n}$equal to the square of $$${n}$. To do this, we must select several suitable candidates for $$${\ mathcal {Z} _n}$whose term is the sought $$${a_n}$.

Let's pick up the first candidate . It is quite simple (in this case), because equality $$${\ mathcal {Z} _n} = n$gives

$$

$$\ begin {align *} {a_0} & = {0} \\ {n} & = {a_n} + n - 1, \ quad {n}> 0 \ end {align *}$$

and we find: $$${a_0} = {0}$and $$${a_n} = 1, \ quad {n}> 0$.
We got the first candidate, let's say $$${x_n}$such that

$$

$$\ begin {align *} {x_0} & = {0} \\ {x_n} & = {1} + {x_ {n-1}}, \ quad {n}> 0 \ tag {2} \ end { align *}$$

By a similar principle, we can find a suitable second candidate who will provide us $$${a_n} =$square from $$${n}$, noting that the sum of natural numbers to the degree $$${k}$usually comes down to something in degree $$${k} + {1}$. Let's pick up $$${\ mathcal {Z} _n} = {n ^ 3}$which gives

$$

$$\ begin {align *} {a_0} & = 0 \\ {n ^ 3} & = {a_n} + {({n} - {1})} ^ 3, \ quad {n}> {0} \ end {align *}$$

and get $$${a_0} = {0}$and $$${a_n} = {3n ^ 2} - {3n} + {1}, \ quad {n}> {0}$.

We got the second candidate, let's say $$$y_n$for which it is true

$$

$$\ begin {align *} {y_0} & = {0} \\ {y_n} & = {3n ^ 2} - {3n} + {1} + {y_ {n-1}}, \ quad {n} > {0} \ tag {3} \ end {align *}$$

We see that $$${y_n}$also contains a linear term in $$${n}$which is unnecessary for us, because we are looking for (following formula (1)) $$${a_n} = {2n ^ 2} + {7}$. Therefore, we will expand our recruitment by a third member, who will provide us $$${a_n}$linear on $$${n}$. This way we will be able to get rid of the linear addend $$${n}$corresponding linear combination of the three members of the set. We will pick up such $$${\ mathcal {Z} _n} = {n ^ 2}$which gives

$$

$$\ begin {align *} a_0 & = 0 \\ n ^ 2 & = a_n + (n-1) ^ 2, \ quad n> 0 \ end {align *}$$

and find $$${a_0} = {0}$and $$${a_n} = {2n} - {1}, \ quad {n}> {0}$.

So we get a third candidate , let's say $$$u_n$for which it is true

$$

$$\ begin {align *} u_0 & = 0 \\ u_n & = 2n-1 + u_ {n-1}, \ quad n> 0 \ tag {4} \ end {align *}$$

Let's take a look at the set:

Overview of the three candidates

$$

$$\ begin {array} {rlcr} \ mathcal {Z} _n && a_n & \\ \ hline \\ x_n = & n \ qquad & 1 & \ qquad \ qquad \ text {acc. to} (2) \\ y_n = & n ^ 3 \ qquad & 3n ^ 2-3n + 1 & \ qquad \ qquad \ text {acc. to} (3) \\ u_n = & n ^ 2 \ qquad & 2n-1 & \ qquad \ qquad \ text {acc. to} (4) \\ \ end {array}$$

Using a suitable linear combination you can notice that

$$

$$\ begin {align *} a_n & = 2n ^ 2 + 7 \\ & = \ frac {2} {3} \ left (3n ^ 2-3n + 1 \ right) + \ left (2n-1 \ right) + \ frac {22} {3} \ end {align *}$$

so we come to

$$

$$\ begin {align *} z_n & = \ frac {22} {3} x_n + \ frac {2} {3} y_n + u_n + c_0 \\ & = \ frac {1} {3} n \ left (2n ^ 2 + 3n + 22 \ right) + c_0 \ end {align *}$$

Note that we need to define a constant. $$$c_0$, given that we also need to meet the initial condition $$$z_0 = 7$. We do it by defining $$$s_0 = 7$and in the end we get:

$$

$$z_n = \ frac {1} {3} n \ left (2n ^ 2 + 3n + 22 \ right) +7, \ quad n \ geq 0$$

To summarize

Description of the set method:
To solve form recurrence

$$

$$\ begin {align *} x_n = f (n) + g (x_ {n-1}, x_ {n-2}, \ ldots, x_0) \ tag {5} \ end {align *}$$

• we find candidates $$$f_1 (n)$, ..., $$$f_k (n)$formulas $$$f (n)$so that they can be linearly reduced to form
  

  $$

  $$f (n) = \ lambda_1 f_1 (n) + \ ldots + \ lambda_k f_k (n)$$
  
  
• after which we consider the generalized representation (5) replacing $$$f (n)$on $$$a_n$
  

  $$

  $$\ mathcal {Z} _n = a_n + g (\ mathcal {Z} _ {n-1}, \ mathcal {Z} _ {n-2}, \ ldots, \ mathcal {Z} _0)$$
  
  
• and solve simpler recurrences
  

  $$

  $$x_n ^ {(l)} = f_l (n) + g (x_ {n-1}, x_ {n-2}, \ ldots, x_0), \ quad 1 \ leq l \ leq k$$
  
  picking up $$$x_n ^ {(l)}$To obtain $$$f_l (n)$.
• Solutions $$$x_n ^ {(l)}$at $$$1 <l <k$form a solution kit $$$x_n$.
• Determine the linear combination
  

  $$

  $$f (n) = \ lambda_1 f_1 (n) + \ ldots + \ lambda_k f_k (n)$$
  
  
• and display the solution
  

  $$

  $$x_n = \ lambda_1 x_n ^ {(1)} + \ ldots + \ lambda_k x_n ^ {(k)} + c_0$$
  
  
• after which we define $$$c_0$according to the initial conditions.

Note: There may be situations in which you have to define more than one initial condition.
Note: It is possible that the set will require further expansion in order to get rid of the extra components that appear when calculating $$$x_n ^ {(l)}$.