This was a question on an assignment presented to my Logic & Mathematics for computer science course, and I am truly baffled as to go on to prove this by double induction:
Consider a string consisting of one or
more decimal digits (0-9). Suppose you
repeatedly insert a 0 to the right of
the leftmost digit and then replace
that string by a string of the same
length which represents the result of
subtracting one from that string.ie: start with string 11 you will get
the following: 11, 101, 100, 1000,
0999, 00999, 00998, and so on.Prove by double induction, that no
matter what string you start with, you
will eventually get a string
containing only 0's.
This question seems rather trivial on first glimpse, however trying to prove it via double induction is another thing for me. I'm having trouble deciding what the variables that I will be applying induction on will be. Obviously one of the two variables will be the string input, but what about the other? I've thought of using length but I don't see what that can do to help. What do you guys think?
Assuming I have encapsulated the variables, I plan on proceeding to prove this in the following manner given for all x and y in N. p(x,y):
Let Q(x) = for all y in N, p(x,y) Let
x be arbitrary and assume for all i in
N, i < x IMPLIES Q(i). We then let y
in N be arbitrary then assume that for
all j in N, j < y implies p(x,j).Afterward I will use the assumption
that for all i and j, p(i,j) is true
such that (i < x) or (i = x and j <
y).Then proceed proof.
Does that skeletal proof structure make logical sense? Double induction is still new to me and it wasn't covered whole lot in lectures so I'm rather still insecure.
I suppose it'd make more sense if we used structural induction on each variable, however we're restricted to use double induction only.
I'm sorry for the long question, I'd appreciate any input & help & insight regarding this question or in double induction in general as my Google-fu seems to be coming short on information of the latter :(.
Best Answer
Let $a$ be the first digit of the string, and let $b$ be the value of the remaining digits. Let's prove that the operation is reducing with respect to the lexical order of $\langle a,b\rangle$, which is one version of interpreting your phrase "double induction."
First, note that the operation of inserting the $0$ to the right of the leading digit affects neither the value of $a$ nor $b$.
Next, note that if $b$ is all zero but $a$ is not $0$, then the operation will end up with $a$ being reduced, because when you subtract one, you will have to borrow from $a$, thereby reducing. Thus, the operation will result with a string having lower $\langle a,b\rangle$ in the lexical order.
If $b$ is not all zero, however, then the operation will end up with the $b$ value being value $1$ less (despite the extra $0$), and so will reduce $\langle a,b\rangle$ in the lexical order.
Since the lexical order on $\mathbb{N}\times\mathbb{N}$ is a well-order, it follows that the operation must eventually hit all $0$s.
The argument shows that you can insert any number of $0$s, rather than just one $0$ at each step, although if you insert more, then it will take longer to get to the all $0$ string, since when you borrow, you will get more $9$s.