# Proof by induction for systems of equations with arithmetic progression

A linear system of equations of the form

$\begin{cases} ux+(u+d)y=u+2d\\ ax+(a+i)y=a+2i\end{cases}$

Will always have the solution $x=-1, y=2$ (easily proven through matrix algebra). How can I prove this by induction?

-
There is no reason to expect induction to work here and it cannot be done directly using induction. Since it's solvable using ring axioms there isn't even any induction involved in proving it. –  quanta Mar 15 '11 at 19:23
@quanta I see. I wondered whether there is an elegant way of proving it by induction, but clearly the a proof based on matrix algebra is far more eligible. Thanks anyway! –  Milosz Wielondek Mar 15 '11 at 19:39
@Milosz: Are $u$, $d$, $a$, and $i$ restricted to nonnegative integers, with at least one nonzero? –  Arturo Magidin Mar 15 '11 at 19:41
@Milosz: The proof uses only simple algebra. Merely substitute $\rm\ X = u,\ Y = d\$ and $\rm\ X = a,\ Y = i\$ in the identity in my above comment. –  Bill Dubuque Mar 15 '11 at 20:10
@Milosz: Induction usually only proves things for positive integers (or for sets of integers of the form $\{a \mid a\geq M\}$ for some integer $M$). You would have to do a fair amount of contorsion to associate such a set to your 4-tuple of integers (perhaps considering $|a|+|d|+|u|+|i|$ and inducting on that), and chances are you'd be better off not using induction in that case. –  Arturo Magidin Mar 15 '11 at 21:53

We can prove this using the induction scheme that says it's true for all $u,d,a,i$ if it's true for $u=d=a=i=1$ and also the (four) induction step(s) given it is true for $(u,d,a,i)$ then it also holds for $(u+1,d,a,i)$, $(u,d+1,a,i)$, $(u,d,a+1,i)$ and $(u,d,a,i+1)$.

The base case will be $a,u,d,i = 1$ $$\begin{cases} x+2y=3\\ x+2y=3\end{cases}$$ clearly the solution holds for this case.

In all four cases the induction hypothesis will be $$\begin{cases} ux+(u+d)y=u+2d\\ ax+(a+i)y=a+2i\end{cases}$$

I will only show one induction step because the other three are so similar

We want to prove

$$\begin{cases} (u+1)x+(u+1+d)y=u+1+2d\\ ax+(a+i)y=a+2i\end{cases}$$

by algebra that's the same as

$$\begin{cases} ux+(u+d)y+x+y=u+2d+1\\ ax+(a+i)y=a+2i\end{cases}$$

and since $x+y = 1$ this reduces to our hypothesis.

-

As proposed by Bill Dubuque, a simple proof can be formulated like this

We substitue $x=-1$ and $y=2$ into $ux+(u+d)y=u+2d$ $\Rightarrow -u+2(u+d)=u+2d$

To prove the above we must show that for $P(u,d)$, every of the following is true: $P(0,0)$, $P(u+1,d)$ and $P(u,d+1)$.

-
Please correct me if I'm wrong! –  Milosz Wielondek Mar 16 '11 at 9:07