Arithmetic About Recursion

Since $S=\frac{k_1}{5^1}+\frac{k_2}{5^2}+\frac{k_3}{5^3}+\frac{k_4}{5^4}+...$ , we have the following:

(1) $2S=\qquad \qquad \quad \frac{2k_1}{5^1}+\frac{2k_2}{5^2}+\frac{2k_3}{5^3}+\frac{2k_4}{5^4}+...$

(2) $5S= \quad \qquad k_1+\frac{k_2}{5^1}+\frac{k_3}{5^2}+\frac{k_4}{5^3}+...$

(3) $25S=5k_1+k_2+\frac{k_3}{5^1}+\frac{k_4}{5^2}+...$

Hence, it is clear that $25S - 5S - 2S = 5k_1 + k_2 - k_1$ , or $18S = 5$ so $S=\frac{5}{18}$ . Thus $a+b=23$ .

The charactersitic equation of the recurrence relation is $x^2-x-2=(x-2)(x+1)=0$ with solutions $2$ and $-1$

Hence, $k_n=A2^n+B(-1)^n$ for some constants $A$ and $B$

For $n=1$ , $k_1=1=2A-B$

For $n=2$ , $k_2=1=4A+B$

Solving for both equations, we get $(A,B)=(\frac{1}{3},-\frac{1}{3})$

Therefore, $k_n = \frac{1}{3}(2^n - (-1)^n)$

$S = \sum \limits_{i=1}^{\infty} \frac{k_i}{5^i} = \frac{1}{3} \sum \limits_{i=1}^{\infty} \frac{2^i - (-1)^i}{5^i} = \frac{1}{3} \sum \limits_{i=1}^{\infty} (\frac{2}{5})^i - (-\frac{1}{5})^i$

$=\frac{1}{3}(\frac{\frac{2}{5}}{1-\frac{2}{5}}-\frac{-\frac{1}{5}}{1-(-\frac{1}{5})}) = \frac{1}{3}(\frac{2}{3}-(-\frac{1}{6})) = \frac{5}{18}$

Here the sequence can be written as $1, 1, 3, 5, 11, 21, 43, 85, 171 .......$ .So, $S = \frac {1}{5^1} + \frac {1}{5^2} + \frac {3}{5^3} + \frac {5}{5^4} + \frac {11}{5^5} .....$ . Now we have to express it as a Geometric Progression to find sum to infinite terms. We observe that every second number is one less than the twice the number preceding it and every number on odd places is one more than twice the number preceding it. So, we separate the numbers on odd places and even places. Let $S_1, S_2$ denote sum of odd and even places respectively. So, $S_1 = \frac {1}{5^1} + \frac {3}{5^3} + \frac {11}{5^5} .............$ and $S_2 = \frac {1}{5^2} + \frac {5}{5^4} + \frac {21}{5^6} .............$ Let us first compute $S_1$ . We intend to make it a GP. So we can rewrite $S_1$ as $S_1 = ( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... ) + ( \frac {0}{5^1} + \frac {1}{5^3} + \frac {3}{5^5} + \frac {11}{5^7} .......)$ $= ( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... ) + \frac {1}{5^2}( \frac {1}{5^1} + \frac {3}{5^3} + \frac {11}{5^5} .......)$ $= ( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... ) + \frac {1}{5^2}( S_1 )$ $= ( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... ) + \frac {1}{5^2}( ( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... ) +\frac {1}{5^2}( S_1 ) )$ . This becomes a GP with first term $( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... )$ and common ratio $\frac {1}{5^2}$ . Sum of infinite terms of GP= $\frac {a}{1 - r}$ where a is first term and r is common ratio. Now let us first compute $( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... )$ . Here apart from $\frac {1}{5^1}$ other numbers are in GP with first term $\frac {2}{5^3}$ and ratio $\frac {5}{5^4}$ . So $( \frac {1}{5^1} + \frac {2}{5^3} + \frac {8}{5^5} + \frac {32}{5^7} ..... )$ = $\frac {1}{5} + \frac { \frac {2}{5^3}}{1 - \frac {4}{5^2}}$ = $\frac {23}{105}$ . So we have $S_1$ as a GP with first term $\frac {23}{105}$ and ratio $\frac {1}{5^2}$ . Therefore $S_1 = \frac {\frac {23}{105}}{1 - \frac {1}{5^2}}$ $= \frac {115}{504}$ .Now $S_2 = \frac {1}{5^2} + \frac {5}{5^4} + \frac {21}{5^6} .............$ $= ( \frac {1}{5^2} + \frac {4}{5^4} + \frac {16}{5^6} ....$ + $\frac {1}{5^4} + \frac {5}{5^6} + \frac {21}{5^8} )$ $= ( \frac {1}{5^2} + \frac {4}{5^4} + \frac {16}{5^6} ....$ + $\frac{1}{5^2}( \frac {1}{5^2} + \frac {5}{5^4} + \frac {21}{5^6}... )$ $= ( \frac {1}{5^2} + \frac {4}{5^4} + \frac {16}{5^6} ....$ + $\frac{1}{5^2}( S_2 )$ . As in the case of $S_1$ this is also a GP with first term $\frac {1}{5^2} + \frac {4}{5^4} + \frac {16}{5^6} ....$ and common ratio $\frac {1}{5^2}$ . Now let us compute $\frac {1}{5^2} + \frac {4}{5^4} + \frac {16}{5^6} ....$ . This is a GP with first term $\frac {1}{5^2}$ and common ratio $\frac {4}{5^2}$ . Therefore $\frac {1}{5^2} + \frac {4}{5^4} + \frac {16}{5^6} ....$ $= \frac {\frac {1}{5^2}}{1 - \frac {4}{5^2}}$ $= \frac {1}{21}$ . So we have $S_2$ as a GP with first term $\frac {1}{21}$ and ratio $\frac {1}{5^2}$ . Therefore $S_2$ = $\frac {\frac {1}{21}}{1 - \frac {1}{5^2}}$ = $\frac {25}{504}$ . Therefore we have $S$ = $S_1 + S_2$ = $\frac {115}{504} + \frac {25}{504}$ $= \frac {140}{504} = \frac {5}{18}$ where 5 and 18 are co-prime. Hence the answer $= 5 +18 = 23$ which is the required answer.

The characteristic equation for the recurrence relation is $x^2 - x - 2 = 0$ . Hence $x = 2$ or $x = -1$ . Therefore $k_n = a(2^n) + b((-1)^n)$

Since $k_1 = k_2 = 1$ , we get $a = \frac{1}{3}, b = -\frac{1}{3}$ . Hence $k_n = \frac{1}{3}(2^n) - \frac{1}{3}((-1)^n)$ .

Hence we can proceed to find the infinite sum $S$ . Now $\displaystyle{S = \sum_{n=1}^{\infty}{\frac{k_n}{5^n}} = \sum_{n=1}^{\infty}{\frac{\frac{1}{3}(2^n) - \frac{1}{3}((-1)^n)}{5^n}}}$ $\displaystyle{=\frac{1}{3}\sum_{n=1}^{\infty}\left (\frac{2}{5} \right )^n - \frac{1}{3}\sum_{n=1}^{\infty}\left (\frac{-1}{5} \right )^n}$ $\displaystyle{=\frac{1}{3}\times\frac{\frac{2}{5}}{1-\frac{2}{5}}-\frac{1}{3}\times\frac{-\frac{1}{5}}{1-(-\frac{1}{5})}}$ $\displaystyle{=\frac{2}{9}+\frac{1}{18}}=\frac{5}{18}$ .

Hence $a + b = 5 + 18 = 23$ .

For a second-order linear recurrence equation of the form $k_n = \alpha k_{n-1} + \beta k_{n-2}$ and $k_1 = k_2 = 1$ , the closed form for $k_n$ is given by

$k_n = \frac{a^n b(1-b)-b^n a(1-b)}{ab(a-b)}$ ,

where $a$ and $b$ are the roots of the quadratic equation $x^2 - \alpha x - \beta = 0$ .

Solving the quadratic equation $x^2-x-2=0$ will give us the roots $2$ and $-1$ .

Thus,

$k_n=\frac{2^n (-1)(1-(-1))-(-1)^n (2)(1-2)}{2(-2)(2-(-1))}$

$k_n=\frac{2^n-(-1)^n}{3}$

Given this formula for $k_n$ , we can easily solve the sum of the series $S=\frac{k_1}{5^1}+\frac{k_2}{5^2}+\frac{k_3}{5^3}+...$ .

$S=\frac{1}{3} \left( \frac{2^1-(-1)^1}{5^1}+\frac{2^2-(-1)^2}{5^2}+\frac{2^3-(-1)^3}{5^3}+… \right)$

$S=\frac{1}{3} \left( \frac{\frac{2}{5}}{1-\frac{2}{5}}-\frac{\frac{-1}{5}}{1-\left(\frac{-1}{5}\right)} \right)$

$S=\frac{5}{18}$

Thus, the answer is $5+18=\boxed{23}$ .

notice that $k_{n+2}=k_{n+1}+2k_{n}$ ,we just multi $S$ with $\frac{2}{5}$ ,then we get $\frac{2}{5}S=\frac{2k_1}{5^2}+\frac{2k_2}{5^3}…$ .

now ignore the $\frac{k_1}{5^1}$ in $S$ and add $\frac{2}{5}S$ with $S$ ,we get $\frac{7}{5}S=\frac{k_1}{5^1}+\frac{k_3}{5^2}+\frac{k_4}{5^3}…$ . It's easy to see that $\frac{k_3}{5^2}+\frac{k_4}{5^3}…$ is a part of $5S=k1+\frac{k_2}{5}+\frac{k_3}{5^2}+\frac{k_4}{5^3}…$ .

now we get a equation: $\frac{7}{5}S=\frac{k_1}{5^1}+5S-k_1-\frac{k_2}{5}$ ,so $\frac{18S}{5}=1$ , $S=\frac{5}{18}$ ,finally $a+b=23$

We first write the initial terms of the given series. They are 1,1,3,5,11,21,43,85,...

Observe that

1=1

1=1*2-1

3=1*4-1

5=1*8-3

11=1*16-5

$k_n$ = $2^{n-1}-k_{n-1}$

Therefore,

S = $\displaystyle \sum_{i=1}^\infty\frac {k_n}{5^n}$

S= $\displaystyle \sum_{i=1}^\infty\frac{2^{i-1}-k_{i-1}}{5^i}$

where we consider $k_0$ to be $0$ .

S= $\displaystyle \sum_{i=1}^\infty\frac{2^{i-1}}{5^i}$ - $\displaystyle \sum_{i=1}^\infty\frac{k_{i-1}}{5^i}$

S= $\displaystyle \sum_{i=1}^\infty\frac{2^{i-1}}{5^i}$ - $\frac{S}{5}$

S = (A geometric Progression with first term 0.2 and common ratio 0.4) - $\frac{S}{5}$

$\frac{6S}{5}$ = $\frac{0.2}{1-0.4}$

or, S = $\frac{5}{18}$

Therfore, the required answer is 23.

Note: The sum of a geometric progression with first term $a$ and common ratio $r$ is equal to $\frac{a}{1-r}$

We can begin by looking for geometric sequences $k_n = k_0 \cdot r^n$ that follow the given recursive rule $k_{n+2}=k_{n+1}+2k_n$ .

For any such sequence, we have $k_0 r^{n+2}=k_0 r^{n+1} + 2k_0 r^n$ , or $r^{n+2}=r^{n+1}+2r^n$ . Dividing by $r^n$ gives $r^2=r+2$ , the solutions to which are $r=2,-1$ . So any geometric sequence with a common ratio of either $2$ or $-1$ will satisfy the recursive rule.

Let $f_n=2^n$ and $g_n=(-1)^n$ . Since these sequences individually satisfy the recursive rule, any linear combination thereof will do so as well. So we want to find values of $a$ and $b$ such that the sequence $a f_n+b g_n$ is identical to the sequence $k_n$ as defined in the problem.

Since $k_1=k_2=1$ , we need $a f_1+b g_1=1$ and $a f_2+b g_2=1$ . This becomes $2a-b=1$ and $4a+b=1$ , the solutions to which are $a=\frac{1}{3}$ and $b=-\frac{1}{3}$ . So an explicit formula for for $k_n$ is given by

$k_n=\frac{1}{3}\cdot 2^n-\frac{1}{3}(-1)^n$ .

The desired infinite sum is

$S=\displaystyle \sum_{n=1}^\infty \frac{k_n}{7^n} = \sum_{n=1}^\infty \left(\frac{1}{3}\left(\frac{2}{7}\right)^n-\frac{1}{3}\left(-\frac{1}{7}\right)^n\right)$ .

This can be split into a difference of two convergent geometric series:

$\displaystyle\frac{1}{3} \sum_{n=1}^\infty \left(\frac{2}{7}\right)^n - \frac{1}{3} \sum_{n=1}^\infty \left(-\frac{1}{7}\right)^n = \frac{1}{3}\left(\frac{2}{5}\right)-\frac{1}{3}\left(-\frac{1}{8}\right)=\frac{7}{40}$ .

So the answer is $7+40=47$ .

$S=k_1/7 + k_2/7^2 + \ldots$ . Let it be equation 1. Now we divide the whole equation by 7. The result is $S/7=k_1/7^2 + k_2/7^3 +\ldots$ . Label this equation 2. Subtracting 2 from 1 we get $6S/7=k_1/7+(k_2-k_1)/7^2+(k_3-k_2)/7^3+ \ldots$ . $6S/7=1/7+(2k_1/7^3+2k_2/7^4+\ldots$ ). Looking at the bracket part, we can write it in the form of $S$ as $2S/7^2$ .We get a single variable equation in $S$ , that is $6S/7=1/7+2S/7^2$ . Now solving for $S$ gives $S=7/40$ . Since we want $a+b$ , the answer is $7+40=49$ .

The recursion $k_{n+2}=k_{n+1}+2k_{n}$ has the characteristic equation $m^2-m-2=0$ which gives the solution $k_n=A2^n+B(-1)^n$ for some constants A and B. Substituting the values of k for n=1 and n=2, we get an explicit solution to the recursion equation: $k_n=\frac{2^n-(-1)^n}{3}$ . Hence, S is given by $\frac{1}{3}$ $[(\frac{2}{7}+\frac{2^2}{7^2}+\ldots)-(\frac{-1}{7}+\frac{1^2}{7^2}-\frac{1}{7^3}+\ldots)]$ = $\frac{1}{3}(\frac{2}{5}+\frac{1}{8})=\frac{7}{40}$ . Thus, the answer is $47$ .

The key idea is to create a combination of S so that as many terms as possible cancel out.

We use the fact that $k_{n+2} - k_{n+1} - 2 k_{n}=0$ to cancel out most of the terms.

$S=\frac{k_1}{7}+\frac{k_2}{7^2}+\frac{k_3}{7^3}+\frac{k_4}{7^4}+...$

$- \frac{S}{7} = - ( \frac{k_1}{7^2}+\frac{k_2}{7^3}+\frac{k_3}{7^4}+...)$

$- \frac{2S}{7^2} = -( \frac{k_1}{7^3}+\frac{k_2}{7^4}+...)$

Adding up both sides we have $\frac{40}{49} \times S=\frac{1}{7} + \frac{1}{7^2} - \frac{1}{7^2}=\frac{1}{7}$

$\therefore S=\frac{7}{40}$

The series is 1/7,1/(7^2),3/(7^3),5/(7^4),11/(7^5),21/(7^6),43/(7^7),85/(7^8).......

We can split the above into two series: 1. 1/(7^1),3/(7^3),11/(7^5),43/(7^7)....... 2. 1/(7^2),5/(7^4),21/(7^6),85/(7^8).......

The sum of first series can be calculated in the following way:

S= 1/(7^1)+3/(7^3)+11/(7^5)+43/(7^7)+........

S*(1/(7^2))= 1/(7^3)+3/(7^5)+11/(7^7)+43/(7^9)+......

On subtracting the two equations we get,

S*(48/49)= 1/(7^1)+ 2/(7^3)+ 8/(7^5)+ 32/(7^7)+........

The above equation from the second term is a GP with first term as 2/(7^3) and common ratio as 4/(7^2). Thus we can find the sum for the above series and get S= (47x7)/(45x48)

Similarly, we can calculate the sum for the second series and get the sum= 49/(48x45)

On adding the above two series we get ((47x7)+ 49)/(48x45)= (54x7)/(45x48)= 7/40. Therefore, a+b=47

If S = \frac{k_1}{7^1} + \frac{k_2}{7^2} + ... , then by using the recursive definition, $S = 0$ $+\frac{k_1}{7^1} + \frac{k_2}{7^2} + \frac{k_2}{7^3} + \frac{k_3}{7^4} + \frac{k_4}{7^5} + ...$
$+\frac{2k_1}{7^3} + \frac{2k_2}{7^4} + \frac{2k_3}{7^5} + ...$ . By grouping, we get:
$S = \frac{k_1}{7^1}+\frac{k_2}{7^2}+\frac{2k_1}{7^3}+\frac{9}{7}(\frac{k_2}{7^3}+\frac{k_3}{7^4} + \frac{k_4}{7^5}+...)$ $=\frac{58}{243} + \frac{9}{49}(S-\frac{1}{7})$ . Putting $S$ on one side, we get $S = \frac{7}{40} \Rightarrow 47$

$2S = \frac {2k_1}{7^1} + \frac {2k_2}{7^2} + \ldots$

$7S = k_1 + \frac {k_2}{7^1} + \frac {k_3}{7^2} + \ldots$

Since $k_{n+2} = k_{n+1} + k_n$ for all $n \geq 1$ ,

By adding, $9S = k_1 + \frac {k_3}{7^1} + \frac {k_4}{7^2} + \ldots$ $= k_1 + 49S - 7k_1 - k_2$

Therefore, $40S = 6k_1 + k_2 = 7 \Rightarrow S = \frac {7}{40}$

First we solve the recurrence relation kn+2=kn+1 + 2 * kn, with k1=k2=1. Setting kn=a^n we get the characteristic equation: a^n+2 =a^n+1 + 2*a^n, which yields a^2-a-2=0. The roots are 2 and -1. That means that the solution of kn is: A1 * 2^n + A2 * (-1)^n . For n=1 and for n=2 we have the initial value 1, so we get that A1=1/3 and A2=-1/3. Setting bn=(kn/7)^n for n=1, 2, 3 … we get bn= 1/3 * (2/7)^n + 1/3 * (-1/7)^n . We want to calculate the infinite sum S=b1 + b2 + b3 + …. Since 2/7 + (2/7)^2 + (2/7)^ + … = 7/5 and (-1/7) + (-1/7)^2 + (-1/7) ^3 + (-1/7)^4 +… = -[ (1/7) + (1/7)^3 + (1/7)^5 +…] + [(1/7)^2 + (1/7)^4 + (1/7)^6 +…] = -7/48 + 1/48 = -6/48= -1/8 we finally get S=(1/3) * (2/5) + (-1/3) * (-1/8 ) =0.1750= 175/1000 =7/40=a/b, where a and b are co primes integers, so a+b=47.

It is clear that all the $k_i$ terms are positive, so $k_i$ are increasing and thus $k_{n+2} = k_{n+1}+2k_n \leq 3 k_{n+1}$ . It follows (by induction or otherwise) that $0 \leq k_i \leq 3^i$ , hence the infinite sum converges to a value between 0 and $\frac {1}{1-\frac {3}{7}}$ . Since all terms are positive, we are allowed to rearrange the terms.

Let $S$ denote the infinite sum. Observe that

$\begin{array}{c}\ 2S & = & & \frac {2} {7 ^1} + & \frac {2} {7 ^2} +& \frac {6} {7 ^3} + & \ldots \\ 7S & = & \frac {1} {7^0} + & \frac {1} {7^1} + & \frac {3} {7^2} + & \frac {5} {7^3} + & \ldots \\ 49S & = \frac {1} {7 ^{-1} } + & \frac {1} {7 ^0} + & \frac {3} {7 ^1} + & \frac {5} {7 ^2} + & \frac {11} {7 ^3} + & \ldots \\ \end{array}$

Hence $49S - 7S - 2S =7$ , or $S = \frac {7} {40}$ . Thus, $a+b=7+40=47$ .

Note: Most students would not show that the sum $S$ is finite. However, this is necessary to justify the validity of the next step.