# Proof of Recursive definition, Analysis 1 by Terence Tao.

I got Proof of a proposition regarding recursive definitions (from Terence Tao's Analysis I) Here i understood that what tao done in the proof. But still i have some confusion.

Question: Why Terence Tao didn't use inductive hypothesis in the proof of proposition 2.1.16?

Also there are some other proofs too where inductive hypothesis is not used and still these are done by induction. How is this possible.

Proposition:2.1.16 (Recursive definition). Suppose for each natural number n, we have some function $$f_n: \mathbb N → \mathbb N$$ . Let c be a natural number. Then we can assign a unique natural number $$a_n$$ to each natural number n, s.t $$a_0=c$$ and $$a_{S(n)}=f_n(a_n)$$ for each natural number n.

Notice : I used $$S(n)$$ instead of $$n++$$.

• I don't understand your question. In that link you provided, the first line of the proof is "We use induction". Commented Jun 30, 2023 at 16:33
• @LeeMosher Yes. Proof is done by induction. But didn't use inductive hypothesis. Commented Jun 30, 2023 at 16:48
• It does use the inductive hypothesis, in the phrase "Now suppose inductively..." Commented Jun 30, 2023 at 16:52
• @LeeMosher Oh. But author didn't use it. He supposed inductively that $a_n$ assigns a unique natural number. Then he didn't use above assumption to show $a_{S(n)}$ has unique value that is $f_n(a_n)$. Commented Jun 30, 2023 at 17:03
• I mean author proved base case that is P(0) is true. Now he has to show that for all n ( P(n) $\implies$ P(S(n)) is true. So he assumed P(n) is true and later didn't use P(n) to show P(S(n)) is true. Commented Jun 30, 2023 at 17:05

Quoting from the proof in the link provided, the inductive hypothesis is used starting in the sentence

Now suppose inductively that the procedure gives a single value to $$a_n$$.

The next sentence completes the induction:

Then the procedure give a single value to $$a_{n++}$$, namely $$f_n(a_n)$$.

Here is a more detailed explanation of that sentence. Knowing from the induction hypothesis that $$a_n$$ has a single value, and knowing from the hypothesis of the proposition that $$f_n$$ is a function, it follows from the definition of a function that $$f_n(a_n)$$ is a single value. That value is then assigned to $$a_{n++}$$, using the assignment statement $$a_{n++} := f_n(a_n)$$. This gives a single value to $$a_{n++}$$ which completes the induction step.

Almost.

In the sentence in parentheses that follows, the author raises an issue: Could one of the later assignment steps $$a_{m++} = f_m(a_m)$$ cause $$a_{n++}$$ to be re-assigned a different value? But this could only happen if $$m\!+\!+=n\!+\!+$$, which by Axiom 2.4 only happens when $$m=n$$. The issue is therefore irrelevant.

• I understood that : if $a_n$ is not unique then $a_{S(n)}$ can't be unique. This is how inductive hypothesis used. Commented Jul 3, 2023 at 6:26