5
$\begingroup$

I am truly baffled as to go on to prove this by double induction:

http://i.stack.imgur.com/Zvrzt.png (snap shot of question)

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?

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 :(.

  • 0
    Source: http://math.stackexchange.com/questions/18455/good-examples-of-double-induction/18480#18480.2011-02-12

1 Answers 1

2

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.

  • 0
    Thanks for the reply. I will try to translate this to the pedantic proof structure my course requires. Given the choice of variables you presented, I will see what I can do!2011-02-12
  • 0
    Probably you just need to go by double induction on $a$ and $b$ as I defined them. The point is that you prove that for any fixed $a$, the claim is true for all $b$. You prove each instance of this by induction on $b$, assuming that the claim is true for all smaller values of $a$.2011-02-12
  • 0
    The case $b=0$ amounts to the borrowing case I mention above, using a smaller value for $a$.2011-02-12
  • 0
    This has a bit of the feel of the proof of Goodstein's theorem to me, though the induction is just over $\omega^2$2011-02-12
  • 0
    Yes, it is similar, but Goodstein's theorem has induction of order type $\epsilon_0$, since every ordinal below $\epsilon_0$ has a finite representation in terms of ordinal additiona, multiplication and exponentiation using only finite numbers and $\omega$.2011-02-12
  • 0
    It is fun to approximate how many steps it takes to reach zero from a given start.2011-02-12
  • 0
    That is an interesting question. Andres Caicedo mentioned that he figured out the corresponding answer for Goodstein sequences, but here it should be much easier. And how much worse is it when you add two $0$s at each step, or add $n$ zeros at step $n$?2011-02-12
  • 0
    @JDH: I think it is roughly 10^10^10^...^b, where there are a levels. The top b should really be $b+\log b+\log \log b + ...$ if you care about that. If you add two 0s the 10s become 100s. You can decide how much worse that is.2011-02-12