## Induction - prove that an explicit function is correct

Study of algorithms, Automata, Programming (Basic, Delphi, C, C++, Assembler, Maple, Mathematica), Software/Hardware, Computational Mathematics, Complexity Theory.

From the same network: MyComputerForum ! Join today !

### Induction - prove that an explicit function is correct

Write down an explicit definition of the function h, where
h(0) = 0 and h(n + 1) = 3 * h(n) + 1.
(Hint: compare to the sequence 1, 3, 9, 27, 81, ....)
Use induction to prove that your formula is correct.

So, I found out that a function f(n) = (3^n - 1) / 2
is the explicit function describing the function h (please correct me if I am wrong).
The problem now is to prove that the function I found is correct.
I have figured out the base step, I think, which was to show that h(1) = f(1).
But about the induction step, am I suppose to show that h(n+1) = f(n+1) ?
Zhai
Newcomer

Posts: 14
Joined: Fri Oct 30, 2009 11:34 am

### Re: Induction - prove that an explicit function is correct

Zhai wrote:But about the induction step, am I suppose to show that h(n+1) = f(n+1) ?

Yes, given that h(n) = f(n) [this is called "weak induction"] or given that h(k) = f(k) for all 1 <= k <= n [this is called "strong induction"].
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12570
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5