Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
2  
@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
1  
@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
show 3 more comments

2 Answers

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|improve this answer
add comment
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|improve this answer
    
Please correct me if I'm wrong! –  Milosz Wielondek Mar 16 '11 at 9:07
add comment

Your Answer

 
discard

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.