Show using induction (coupled linear recurrences)

Question

Some homework help would be greatly appreciated, took a screenshot and made an image to make it easier to show and get help with.

(2) Consider the numbers defined recursively by $a_1=3$, $c_1=5$, $$a_{n+1}=3a_n+2c_n+1\text{ and }c_{n+1}=4a_n+3c_n+2\;.$$ Show using induction that for all $n\in\Bbb Z^+$, $$a_n^2+(a_n+1)^2=c_n^2\;.$$

What have you done? Since this is induction, what are you stuck at? — Calvin Lin, May 14 '13 at 21:51
could you at least try writing out the base case and the inductive step you wish to achieve? — Alex R., May 14 '13 at 21:52

score 2 · Answer 1 · answered May 14 '13 at 22:12

My guess is that you were too lazy to do the expansions.

Here's a way that you don't have to fully expand out everything.

$c_{n+1} ^2 = (4 a_n + 3 c_n + 2)^2 = (4a_n +2)^2 + 2 ( 4 a_n +2) (3 c_n) + 9 c_n^2$

$a_{n+1}^2 + (a_{n+1} +1)^2 = (3a_n+1) ^2 + (3a_n+2)^2 + 2 (6a_n + 3)(2c_n) + 8 c_n^2 $

We want to show that the RHS is equal to each other. This is equivalent to $$c_n^2 = 2 a_n ^2 + 2 a_n + 1,$$

which is true by the induction hypothesis. Hence, the LHS is equal to each other and we are done.

score 1 · Answer 2 · answered May 14 '13 at 22:00

Let $P(n)$ be the statement that $a_n^2+(a_n+1)^2=c_n^2$; you want to prove that $P(n)$ is true for all $n\ge 1$. You can easily check that $P(1)$ is true: that’s just arithmetic. For the induction step you need to let $n\ge 1$ be arbitrary, assume that $P(n)$ is true, and somehow use that assumption to prove that $P(n+1)$ must then also be true. In other words, your induction hypothesis will be that

$$a_n^2+(a_n+1)^2=c_n^2\;,\tag{1}$$

where $n$ is some unspecified positive integer, and from this you’ll try to prove that

$$a_{n+1}^2+(a_{n+1}+1)^2=c_{n+1}^2\;.$$

You’ll do this by using the recurrences to expand $a_{n+1}$ and $c_{n+1}$ in terms of $a_n$ and $c_n$ and using the relation ship between $a_n$ and $c_n$ assumed in $(1)$.

Show using induction (coupled linear recurrences)

2 Answers2