4
$\begingroup$

The solution of $\frac{a_{20}}{a_{20}+b_{20}}$ is $-39$ (This is wrote by answer sheet) from the recursive system of equations :

\begin{cases} a_{n+1}=-2a_n-4b_n \\ b_{n+1}=4a_n+6b_n\\ a_0=1,b_0=0 \end{cases}

This is taken from $2007$ GATE entrance exam in India.

anyone can show me how we can calculate this answer?

Update 1:

Three answer is added, but my main problem is remains up to yet, non of these three answers didn't include the main aspect of this question. my main problem is via simplification and replacement in last part of solution.

$\endgroup$
  • $\begingroup$ Are you sure the question had $\frac{a_{20}}{a_{20}+a_{20}}$?? Looks strange. $\endgroup$ – SchrodingersCat Jul 27 '16 at 9:06
  • $\begingroup$ What you've written is $1/2$ if $a_{20} \neq 0$. $\endgroup$ – Ahmed S. Attaalla Jul 27 '16 at 9:24
  • $\begingroup$ You've written $\frac{a_{20}}{a_{20}+a_{20}}$ this is equal to $1/2$ considering $a_{20} \neq 0$. I think you want something else. $\endgroup$ – Ahmed S. Attaalla Jul 27 '16 at 12:45
1
$\begingroup$

$$a_{n+1}=-2a_n-4b_n \tag1$$ $$b_{n+1}=4a_n+6b_n \tag2$$ $$a_0=1,b_0=1 \tag3$$

$$(1) + (2) \implies a_{n+1}+b_{n+1}=2a_n+2b_n=2(a_n+b_n) $$ $$\implies \frac{a_{n+1}+b_{n+1}}{a_n+b_n}=2$$

Similarly we have $$\frac{a_{n}+b_{n}}{a_{n-1}+b_{n-1}}=\frac{a_{n-1}+b_{n-1}}{a_{n-2}+b_{n-2}}=\ldots=\frac{a_1+b_1}{a_0+b_0}=2$$

Therefore we can write that $$\frac{a_{n+1}+b_{n+1}}{a_n+b_n}\cdot\frac{a_{n}+b_{n}}{a_{n-1}+b_{n-1}}\cdot\frac{a_{n-1}+b_{n-1}}{a_{n-2}+b_{n-2}} \ldots \frac{a_1+b_1}{a_0+b_0}=2\cdot2\cdot2\ldots2$$ $$\implies \frac{a_{n+1}+b_{n+1}}{a_0+b_0}=2^{n+1}$$ $$\implies \frac{a_{n+1}+b_{n+1}}{1+1}=2^{n+1}$$ $$\implies a_{n+1}+b_{n+1}=2^{n+2}$$

So, $$a_{20}+b_{20}=2^{21}$$

Now, you can find $a_n$ from the relation $a_{n+2}-4a_{n+1}+4a_n=0$ by using the power series method. And using the above relation, you can deduce $b_n$.

Hope this helps.

$\endgroup$
  • $\begingroup$ But OP is not familiar with methods for solving that last equation. $\endgroup$ – Gerry Myerson Jul 27 '16 at 9:18
  • $\begingroup$ Yes @GerryMyerson Exactly, maybe my problem via the last part. $\endgroup$ – user355834 Jul 27 '16 at 9:19
  • $\begingroup$ would you please show me how I find $a_n$ and $b_n$? $\endgroup$ – user355834 Jul 27 '16 at 15:22
  • $\begingroup$ @user355834 Check this link ..... math.cmu.edu/~af1p/Teaching/Combinatorics/Slides/… See if this helps. $\endgroup$ – SchrodingersCat Jul 27 '16 at 15:31
  • $\begingroup$ No idea on complete this answer? $\endgroup$ – user355834 Jul 29 '16 at 22:56
1
$\begingroup$

Hint :

show that

$$\frac{a_{n+1}}{a_{n+1}+b_{n+1}}=-2+\frac{a_{n}}{a_{n}+b_{n}}$$

$\endgroup$
  • $\begingroup$ As apparently you want $a_{20}/(a_{20}+b_{20})$ (a misprint in your question ?), it is natural to look at $a_n/(a_n+b_n)$. $\endgroup$ – Kelenner Jul 27 '16 at 9:28
  • $\begingroup$ I do not understand "via solving the last part " $\endgroup$ – Kelenner Jul 27 '16 at 9:31
  • $\begingroup$ How do you get -39 though ? Given a0, b0 = 1, I'd say that a0/(a0+b0) is 1/2, and thus the a20/(a20+20) should be -39.5... $\endgroup$ – Urukann Jul 27 '16 at 9:43
  • $\begingroup$ I have seen. But the computation for the formula is good. It remain the case that the sequence $a_n/(a_n+b_n)$ is not well defined, ie that there exists $k\leq 20$ with $a_k+b_k=0$, or a misprint in the question..; $\endgroup$ – Kelenner Jul 27 '16 at 9:55
  • $\begingroup$ ?? Simply replace $a_{n+1}$ and $b_{n+1}$ by their expressions in function of $a_n$ and $b_n$, and compute. Have you verified $a_{20}/(a_{20}+a_{20})$ and the final result (-$39$) ? $\endgroup$ – Kelenner Jul 27 '16 at 10:34
1
$\begingroup$

$4b_n=-a_{n+1}-2a_n$, $4b_{n+1}=-a_{n+2}-2a_{n+1}$, $-a_{n+2}-2a_{n+1}=16a_n-6a_{n+1}-12a_n$, $a_{n+2}-4a_{n+1}+4a_n=0$. Do you know how to solve that kind of recurrence?

Here's an approach. $a_{n+2}-4a_{n+1}+4a_n=(a_{n+2}-2a_{n+1})-2(a_{n+1}-2a_n)=c_{n+1}-2c_n$, where we are defining $c_n$ by $c_n=a_{n+1}-2a_n$. Now we have to solve $c_{n+1}-2c_n=0$, and the solution is obviously $c_n=c_02^n$ (and we can work out $c_0$ easily enough). So now we have to solve $a_{n+1}-2a_n=c_02^n$. Are we at a recurrence you can solve yet?

$\endgroup$
  • $\begingroup$ If you aren't familiar with second-order, linear, constant-coefficient, homogeneous recurrence relations (like the one for the Fibonacci numbers, $f_{n+1}-f_n-f_{n-1}=0$), then I guess this is not the way to go. $\endgroup$ – Gerry Myerson Jul 27 '16 at 9:17
  • $\begingroup$ I think if you want to have any success with problems like the one you pose, you first have to learn how to solve simple recurrences. There are dozens of books on discrete math that have chapters on these equations, and there are dozens of questions that have been asked and answered on this website. There's no point in my posting a treatise on how to solve first-order linear constant-coefficient recurrences, when there is so much about them on this website already. Anyway, I think @Kelenner may have the best idea on this problem. $\endgroup$ – Gerry Myerson Jul 27 '16 at 12:35
  • $\begingroup$ Would you please show me the next step? As I say in first time, my problem is via solving it. thanks $\endgroup$ – user355834 Jul 28 '16 at 11:28
  • $\begingroup$ The next step is to get yourself a good textbook on discrete mathematics, and read the chapter on recurrence relations. $\endgroup$ – Gerry Myerson Jul 28 '16 at 12:38
  • $\begingroup$ I read it but no progress math.cmu.edu/~af1p/Teaching/Combinatorics/Slides/… $\endgroup$ – user355834 Jul 28 '16 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.