1

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?

Milo Wielondek
  • 1,919
  • 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! – Milo 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
  • 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? – Bill Dubuque Mar 15 '11 at 19:41
  • @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. – Milo Wielondek Mar 15 '11 at 20:07
  • 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
  • @Bill ingeniously simple! Thanks, I'll give it a go. – Milo Wielondek Mar 15 '11 at 20:17
  • 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

2 Answers2

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.

quanta
  • 12,425
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)$.

Milo Wielondek
  • 1,919