Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
up vote 0 down vote accepted

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)$.

share|cite|improve this answer
Please correct me if I'm wrong! – Milosz Wielondek Mar 16 '11 at 9:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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