4
$\begingroup$

Let $\omega$ denote the natural numbers (intersection of all inductive set) . Assume $h$ is the function from $\omega$ into $\omega$ for which $h(0)=1$ and $h(n^+)=h(n)+3$ . Give an explicit (not recursive) expression for $h(n)$.

Informally , we have $h(n^+)+h(n)+...+h(1)=h(n)+3+...+h(0)+3$ then we find that $h(n^+)$ "should be" $3n+4$ , so we guess $h(n)=3n+1$ . Then we can apply induction and recursion theorem to get the desired conclusion .
However , I don't like the proof above since we have to guess what $h(n)$ might be first . Can we prove it directly ?

Note: This is an exercise of set theory , so the proof need to be rigorous . Sentence such as "$0+1+...+n$" should be avoid .

$\endgroup$
7
$\begingroup$

You need to distinguish between knowing what to prove and actually proving it.

Actual proofs can be required to be rigorous, but there is no standard of rigor for finding out what to prove. Any kind of hunches, sloppy notation, and weird intuitive leaps are allowed in that phase as long as the actual proof you do at the end is rigorous.

It is very easy to prove -- with all the rigor you'd care to demand -- the fact that $h(n) = 1+3n$ is a solution to your condition, and in fact the only solution on $\mathbb N$.

But here you are instead demanding to have some kind of rigor in knowing that it would be a good idea to attempt such a proof. This demand is foreign to mathematics, and you will run yourself into numerous dead ends in your mathematical education if you keep expecting such demands to be satisfiable.

Your confusion is unfortunately not uncommon among students who have gotten an impression from school that mathematics is about following particular procedures for each problem type. You then get confused when you're asked to investigate a problem without having a procedure to follow. But there are no procedures in general -- to the extent mathematics is about rules at all, it is about investigating what the rules will let you get away with, not about letting the rules tell you what to do with them.


For the concrete question, we could point you towards a general step-by-step procedure for solving linear recurrences. And we could even prove rigorously that said procedure works in general -- but you could still complain that one needs to "guess" a description of that procedure before one can start proving that it works.

$\endgroup$
  • $\begingroup$ +1 Beautifully said. $\endgroup$ – Haris Gušić Jun 26 '19 at 9:33
5
$\begingroup$

How about this

$$\displaystyle \sum_{n=1}^{N} h(n) = \displaystyle \sum_{n=1}^{N} \big(h(n-1)+3 \big) = \displaystyle \sum_{n=0}^{N-1} \big(h(n)+3 \big) = h(0) + 3n + \displaystyle \sum_{n=1}^{N-1} h(n) = 1+3n +\displaystyle \sum_{n=1}^{N-1} h(n)$$

Subtracting the sum from both sides gives $$ h(n) = 3n+1$$

$\endgroup$
  • $\begingroup$ Well done ! (+1) $\endgroup$ – Peter Jun 26 '19 at 8:51
  • $\begingroup$ I think we need to define $\sum$ first . Although we all know what $\sum_1^N$ mean in analysis , it has to be defined explicitly in set theory . The definition $\sum_1^n h(n)=h(1)+h(2)+...+h(n)$ is impossible since "..." is not well defined . $\endgroup$ – J.Guo Jun 26 '19 at 8:56
  • $\begingroup$ $h(n)$ is well defined because the recurrence relations clearly defines the values inductively (no matter whether we know how) , and therefore the sum over them is well defined as well. To my opinion, this is a perfect answer. $\endgroup$ – Peter Jun 26 '19 at 8:59
  • $\begingroup$ @ Peter I see $h(n)$ is well defined . I mean "..." is not well defined since we can not write a proof in set theory like $f(n)=1+2+...+n$ . $\endgroup$ – J.Guo Jun 26 '19 at 9:03
1
$\begingroup$

With simple problems like this one you can just try to unravel the sequence.

$$h(n+1)=3+h(n)=\underbrace{3+3}_{n+1-(n-1)}+h(n-1)=\underbrace{3+3+3}_{n+1-(n-2)}+h(n-2)=\cdots$$ $$=\underbrace{3+3+\cdots+3}_{n+1-0}+h(0)=3(n+1)+1$$ Now just replace $n+1$ with $n$ and you get $h(n)=3n+1$. Now you can rigorously prove this using induction.

Note that the numbers under the braces represent the number of terms.

$\endgroup$
  • $\begingroup$ This is a nice answer in analysis . However , it is not an answer in set theory since we can not define "..." . $\endgroup$ – J.Guo Jun 26 '19 at 8:58
  • $\begingroup$ @J.Guo Then you can apply induction to prove it rigorously. The method I showed serves only as an "intuition booster". $\endgroup$ – Haris Gušić Jun 26 '19 at 9:14
  • $\begingroup$ @ Haris Gušić Yes , that was why I write down the word "informally" in my post . However , I want an answer which can solve this question directly . $\endgroup$ – J.Guo Jun 26 '19 at 9:15
0
$\begingroup$

Using the Z transform, the sequence $ h_{n+1} = h_n+3 $ becomes: $$ zH(z)-zh_0 = H(z)+\frac{3z}{z-1} $$ $$ H(z) = \frac{3z}{(z-1)^2}+\frac{z}{z-1} $$ Taking the inverse Z transform of the above expression we get: $$ h_n = 3n+1 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.