1
$\begingroup$

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?

  • 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.2011-03-15

2 Answers 2

0

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

  • 0
    Please correct me if I'm wrong!2011-03-16
1

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.