My Math Forum Induction - prove that an explicit function is correct

 Computer Science Computer Science Forum

 February 14th, 2012, 05:08 AM #1 Newbie   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) ?
February 14th, 2012, 10:31 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
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"].

 Tags correct, explicit, function, induction, prove

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Albert.Teng Algebra 4 November 9th, 2013 06:47 AM philip Algebra 10 January 14th, 2012 05:08 AM Sissy Applied Math 2 November 25th, 2010 09:55 AM khyratmath123 Math Software 1 January 27th, 2010 04:28 PM khyratmath123 Calculus 4 January 10th, 2010 05:16 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top