Induction and Recursion.. I have NO idea!


by 1MileCrash
Tags: induction, recursion
1MileCrash
1MileCrash is offline
#1
Mar8-12, 06:14 PM
1MileCrash's Avatar
P: 1,227
I think I'm pretty good at standard induction. Never had a problem.

Induction and recursion is mercilessly whooping my ***.

1. The problem statement, all variables and given/known data

Let a1 = 1. For each natural number n > 1, let an = 3an-1 - 1.

Prove that for each natural number n, an = 1/2(3n-1 + 1)

2. Relevant equations



3. The attempt at a solution

WAT

I can "build it." And I don't even feel comfortable doing that. Let S be the set of n for which the theorem holds.

Let n = 2

Theorem holds.

Let n = 3

Theorem holds.

So 2,3 are elements of S.

(Do I have to show it for 2? Or more? Or just one? Why?)

Suppose that n >= 3 and {1,2,....,n} is a subset of S.

I have no idea what to do. At all. Can someone please explain recursion induction to me?
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
1MileCrash
1MileCrash is offline
#2
Mar8-12, 06:56 PM
1MileCrash's Avatar
P: 1,227
I think I see..

I know that
an+1 = 3an - 1 because that's the definition.

And based on my assumption, an = 1/2(3[SUP]n-1[/SUP + 1)

So I can plug it in, and algebraically show that an+1 equals 1/2(3[SUP]n[/SUP + 1)

Am I on the right track?
micromass
micromass is online now
#3
Mar8-12, 06:57 PM
Mentor
micromass's Avatar
P: 16,701
Yes, that's the idea. Can you do that?

1MileCrash
1MileCrash is offline
#4
Mar8-12, 06:58 PM
1MileCrash's Avatar
P: 1,227

Induction and Recursion.. I have NO idea!


Yes, that's what I tried and it worked out.

So for this example, I'd really only need to show it to be true for one value, right?
micromass
micromass is online now
#5
Mar8-12, 07:01 PM
Mentor
micromass's Avatar
P: 16,701
Quote Quote by 1MileCrash View Post
Yes, that's what I tried and it worked out.

So for this example, I'd really only need to show it to be true for one value, right?
Yes, you only need to show it's true for n=1 and you need to show the induction step.
1MileCrash
1MileCrash is offline
#6
Mar8-12, 07:02 PM
1MileCrash's Avatar
P: 1,227
Do you mean n = 2? If n = 1, an-1 is undefined?
micromass
micromass is online now
#7
Mar8-12, 07:04 PM
Mentor
micromass's Avatar
P: 16,701
Quote Quote by 1MileCrash View Post
Do you mean n = 2? If n = 1, an-1 is undefined?
Yes, check it for n=2 of course.
1MileCrash
1MileCrash is offline
#8
Mar8-12, 07:07 PM
1MileCrash's Avatar
P: 1,227
Ok, got it. Thanks again!


Register to reply

Related Discussions
Need help creating a recursive script in matlab that can do this: Math & Science Software 1
Recursion in C Programming & Computer Science 12
function is F(n) = n(n+1) General Math 4
C++ fun with recursion Computing & Technology 17
What is the largest number of pieces you can get by cutting a pizza Introductory Physics Homework 1