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
    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.2011-03-15
  • 0
    @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!2011-03-15
  • 0
    @Milosz: Are $u$, $d$, $a$, and $i$ restricted to nonnegative integers, with at least one nonzero?2011-03-15
  • 0
    It amounts to proving that $\rm\ -X + 2\ (X+Y)\ =\ X + 2\ Y\:.\ $ Certainly you could prove that by induction if you are given that $\rm\ u,d,a,i\ $ are arbitrary naturals, but it's not clear that you are working at such a low foundational level. Please give more context for your query. Why are you seeking a proof by induction? Are $\rm\ u,d,a,i\ $ arbitrary naturals, or integers, or what?2011-03-15
  • 0
    @Bill,Arturo u,d,a,i are integers. I'm writing a short paper on this type of equations and I would like to know whether it can be proven by induction, which I thought would be more elegant than my existent proof by matrix algebra.2011-03-15
  • 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.2011-03-15
  • 0
    @Bill ingeniously simple! Thanks, I'll give it a go.2011-03-15
  • 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.