My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

Reply
 
LinkBack Thread Tools Display Modes
February 14th, 2012, 06:08 AM   #1
 
Joined: Oct 2009

Posts: 14
Thanks: 0

Induction - prove that an explicit function is correct

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 is offline  
 
February 14th, 2012, 11:31 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 12,859
Thanks: 94

Re: Induction - prove that an explicit function is correct

Quote:
Originally Posted by Zhai
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"].
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
correct, explicit, function, induction, prove


Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
prove : the student's answer is not correct Albert.Teng Algebra 4 November 9th, 2013 07:47 AM
Proving explicit function philip Algebra 10 January 14th, 2012 06:08 AM
Prove by induction Sissy Applied Math 2 November 25th, 2010 10:55 AM
is it an explicit function? khyratmath123 Math Software 1 January 27th, 2010 05:28 PM
is it an explicit function or not? khyratmath123 Calculus 4 January 10th, 2010 06:16 AM





Copyright © 2014 My Math Forum. All rights reserved.