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

Postby Zhai » Tue Feb 14, 2012 9:08 am

The task:
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
Newcomer
 
Posts: 14
Joined: Fri Oct 30, 2009 11:34 am

Re: Induction - prove that an explicit function is correct

Postby CRGreathouse » Tue Feb 14, 2012 2:31 pm

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/~bill/mingw/PARI-2-6.exe
User avatar
CRGreathouse
Global Moderator
Global Moderator
 
Posts: 10691
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5


Return to Computer Science

Who is online

Users browsing this forum: No registered users and 2 guests