Solution 1. Extend the definitions also for n = 1 , 2 n=1,2 n = 1 , 2 . Consider the following sets
A n ′ = { ( x 1 , x 2 , … , x n ) ∈ A n : x n − 1 = x n } , A n ′ ′ = A n ∖ A n ′ , A'_n=\{(x_1,x_2,\dots,x_n)\in A_n : x_{n-1}=x_n\},\quad A''_n=A_n\setminus A'_n, A n ′ = {( x 1 , x 2 , … , x n ) ∈ A n : x n − 1 = x n } , A n ′′ = A n ∖ A n ′ ,
B n ′ = { ( x 1 , x 2 , … , x n ) ∈ B n : x n = 0 } , B n ′ ′ = B n ∖ B n ′ B'_n=\{(x_1,x_2,\dots,x_n)\in B_n : x_n=0\},\quad B''_n=B_n\setminus B'_n B n ′ = {( x 1 , x 2 , … , x n ) ∈ B n : x n = 0 } , B n ′′ = B n ∖ B n ′
and denote
a n = ∣ A n ∣ a_n=|A_n| a n = ∣ A n ∣ ,
a n ′ = ∣ A n ′ ∣ a'_n=|A'_n| a n ′ = ∣ A n ′ ∣ ,
a n ′ ′ = ∣ A n ′ ′ ∣ a''_n=|A''_n| a n ′′ = ∣ A n ′′ ∣ ,
b n = ∣ B n ∣ b_n=|B_n| b n = ∣ B n ∣ ,
b n ′ = ∣ B n ′ ∣ b'_n=|B'_n| b n ′ = ∣ B n ′ ∣ ,
b n ′ ′ = ∣ B n ′ ′ ∣ b''_n=|B''_n| b n ′′ = ∣ B n ′′ ∣ .
It is easy to observe the following relations between the a a a –sequences
{ a n = a n ′ + a n ′ ′ a n + 1 ′ = a n ′ ′ a n + 1 ′ ′ = 2 a n ′ + 2 a n ′ ′ , \left\{\begin{array}{rcl} a_n &=& a'_n+a''_n\\ a'_{n+1} &=& a''_n\\ a''_{n+1} &=& 2a'_n+2a''_n \end{array}\right., ⎩ ⎨ ⎧ a n a n + 1 ′ a n + 1 ′′ = = = a n ′ + a n ′′ a n ′′ 2 a n ′ + 2 a n ′′ ,
which lead to
a n + 1 = 2 a n + 2 a n − 1 a_{n+1}=2a_n+2a_{n-1} a n + 1 = 2 a n + 2 a n − 1 .
For the b b b –sequences we have the same relations
{ b n = b n ′ + b n ′ ′ b n + 1 ′ = b n ′ ′ b n + 1 ′ ′ = 2 b n ′ + 2 b n ′ ′ , \left\{\begin{array}{rcl} b_n &=& b'_n+b''_n\\ b'_{n+1} &=& b''_n\\ b''_{n+1} &=& 2b'_n+2b''_n \end{array}\right., ⎩ ⎨ ⎧ b n b n + 1 ′ b n + 1 ′′ = = = b n ′ + b n ′′ b n ′′ 2 b n ′ + 2 b n ′′ ,
therefore
b n + 1 = 2 b n + 2 b n − 1 b_{n+1}=2b_n+2b_{n-1} b n + 1 = 2 b n + 2 b n − 1 .
By computing the first values of ( a n ) (a_n) ( a n ) and ( b n ) (b_n) ( b n ) we obtain
{ a 1 = 3 , a 2 = 9 , a 3 = 24 b 1 = 3 , b 2 = 8 \left\{\begin{array}{l} a_1=3,\quad a_2=9,\quad a_3=24\\ \qquad b_1=3,\quad b_2=8 \end{array}\right. { a 1 = 3 , a 2 = 9 , a 3 = 24 b 1 = 3 , b 2 = 8
which leads to
{ a 2 = 3 b 1 a 3 = 3 b 2 \left\{\begin{array}{l} a_2=3b_1\\ a_3=3b_2 \end{array}\right. { a 2 = 3 b 1 a 3 = 3 b 2
Now, reasoning by induction, it is easy to prove that
a n + 1 = 3 b n a_{n+1}=3b_n a n + 1 = 3 b n for every
n ≥ 1 n\ge1 n ≥ 1 .
Solution 2. Regarding x i x_i x i to be elements of Z 3 \mathbb{Z}_3 Z 3 and working "modulo 3", we have that
( x 1 , x 2 , … , x n ) ∈ A n ⇒ ( x 1 + 1 , x 2 + 1 , … , x n + 1 ) ∈ A n , ( x 1 + 2 , x 2 + 2 , … , x n + 2 ) ∈ A n (x_1,x_2,\dots,x_n)\in A_n\Rightarrow (x_1+1,x_2+1,\dots,x_n+1)\in A_n,\ (x_1+2,x_2+2,\dots,x_n+2)\in A_n ( x 1 , x 2 , … , x n ) ∈ A n ⇒ ( x 1 + 1 , x 2 + 1 , … , x n + 1 ) ∈ A n , ( x 1 + 2 , x 2 + 2 , … , x n + 2 ) ∈ A n
which means that
1 / 3 1/3 1/3 of the elements of
A n A_n A n start with 0. We establish a bijection between the subset of all the vectors in
A n + 1 A_{n+1} A n + 1 which start with 0 and the set
B n B_n B n by
( 0 , x 1 , x 2 , … , x n ) ∈ A n + 1 ⟼ ( y 1 , y 2 , … , y n ) ∈ B n y 1 = x 1 , y 2 = x 2 − x 1 , y 3 = x 3 − x 2 , … , y n = x n − x n − 1 \begin{gathered} (0,x_1,x_2,\dots,x_n)\in A_{n+1}\longmapsto (y_1,y_2,\dots,y_n)\in B_n\\ y_1=x_1,\, y_2=x_2-x_1,\, y_3=x_3-x_2,\dots,y_n=x_n-x_{n-1} \end{gathered} ( 0 , x 1 , x 2 , … , x n ) ∈ A n + 1 ⟼ ( y 1 , y 2 , … , y n ) ∈ B n y 1 = x 1 , y 2 = x 2 − x 1 , y 3 = x 3 − x 2 , … , y n = x n − x n − 1
(if
y k = y k + 1 = 0 y_k=y_{k+1}=0 y k = y k + 1 = 0 then
x k − x k − 1 = x k + 1 − x k = 0 x_k-x_{k-1}=x_{k+1}-x_k=0 x k − x k − 1 = x k + 1 − x k = 0 (where
x 0 = 0 x_0=0 x 0 = 0 ), which gives
x k − 1 = x k = x k + 1 x_{k-1}=x_k=x_{k+1} x k − 1 = x k = x k + 1 , which is not possible because of the definition of the sets
A p A_p A p ; therefore, the definition of the above function is correct).
The inverse is defined by
( y 1 , y 2 , … , y n ) ∈ B n ⟼ ( 0 , x 1 , x 2 , … , x n ) ∈ A n + 1 x 1 = y 1 , x 2 = y 1 + y 2 , … , x n = y 1 + y 2 + ⋯ + y n \begin{gathered} (y_1,y_2,\dots,y_n)\in B_n\longmapsto (0,x_1,x_2,\dots,x_n)\in A_{n+1}\\ x_1=y_1,\, x_2=y_1+y_2,\dots,x_n=y_1+y_2+\dots+y_n \end{gathered} ( y 1 , y 2 , … , y n ) ∈ B n ⟼ ( 0 , x 1 , x 2 , … , x n ) ∈ A n + 1 x 1 = y 1 , x 2 = y 1 + y 2 , … , x n = y 1 + y 2 + ⋯ + y n
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 1–2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.