Induction and Recursion I have NO idea

In summary, the speaker is discussing their understanding of standard induction and how they have never had a problem with it. However, they are struggling with induction and recursion and need help understanding it. The conversation then shifts to discussing a specific example of recursion induction and the speaker's progress in understanding it. They are able to prove the theorem for one value and only need to show the induction step to prove it for all values.
  • #1
1MileCrash
1,342
41
I think I'm pretty good at standard induction. Never had a problem.

Induction and recursion is mercilessly whooping my ***.

Homework Statement



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)

Homework Equations





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?
 
Physics news on Phys.org
  • #2
I think I see..

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

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

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

Am I on the right track?
 
  • #3
Yes, that's the idea. Can you do that?
 
  • #4
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?
 
  • #5
1MileCrash said:
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.
 
  • #6
Do you mean n = 2? If n = 1, an-1 is undefined?
 
  • #7
1MileCrash said:
Do you mean n = 2? If n = 1, an-1 is undefined?

Yes, check it for n=2 of course.
 
  • #8
Ok, got it. Thanks again!
 

1. What is induction and recursion?

Induction and recursion are mathematical techniques used to prove statements or solve problems by breaking them down into smaller parts and then showing that they hold true for those parts.

2. How does induction work?

Induction is based on the principle that if a statement is true for a particular number or case (known as the base case), and it can be shown that if the statement is true for a certain case, then it is also true for the next case, then the statement must be true for all cases.

3. What is the difference between mathematical induction and structural induction?

Mathematical induction is used to prove statements about numbers, while structural induction is used to prove statements about structures or objects, such as trees or graphs.

4. What is the role of the base case in induction and recursion?

The base case is the starting point for the proof or solution. It is the case for which the statement is assumed to be true and serves as the foundation for the rest of the proof.

5. How are induction and recursion used in computer science?

Induction and recursion are fundamental concepts in computer science and are used in a variety of algorithms and data structures, such as sorting and searching algorithms, as well as in the design and analysis of programs.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
981
  • Calculus and Beyond Homework Help
Replies
4
Views
986
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
449
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
532
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top