Induction

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/11

encourage image

There's no tags or description

Looks like no tags are added yet.

12 Terms

1
New cards

What is the equation for induction? When can it be used?

[n(n+1)]/2. It c an be used when going to the nth term in a summation

2
New cards

Definition: Method of Induction

Given a statement, it proves the base case and the inductive case

3
New cards

Definition: Base case

Proving the first integer in a summation to be true in terms/equal to the equation of induction

4
New cards

Definition: Inductive case

Proving all consecutive integers also follow the rule that we claim to be true (if we have n, then prove n+1 works as well)

5
New cards

T/F: The equation for induction works for summations going to n+1

False. You would have to take out the n+1 term and add it separately on both sides of the equation

6
New cards

Steps for proof by induction?

1) Prove a base case using the first integer (look at the BOTTOM of a summation)

2) Prove the induction case to be true:

  • First, assume your proof in k terms (switch out every n for k) is true

  • Then, mathematically, solve the equation to prove it is true for consecutive integers


7
New cards

What do you HAVE to declare when doing these kinds of proofs?

Where you are using the inductive hypothesis (hew will take off points)

8
New cards

Definition: Telescoping Product

A product in which the denominator of the previous term cancels out the numerator of the next term

9
New cards

Definition: Pre-condition

The initial state of a function

10
New cards

Definition: Post-condition

What is returned after a function

11
New cards

What determines the correctness of a loop?

Variables satisfy the pre-condition/base case, the loop terminates after a finite number of repetitions, and the post-condition (inductive case) is the one we expect

12
New cards

What is considered an “incorrect loop”?

One where a expected input yields an unexpected output (ex/ infinite loop)