1. ## Induction

http://prntscr.com/fqo97b

For this, the marking guidelines says n=1,2,3 is obviously true so they prove base case n = 4
They assume true for n = k for k>=5
Prove true for n = k + 1

Would it be alright to do base case as n = 1
Assume true for n = k, n = k+1, n = k+2
Then prove true for n = k + 3
I did this and it worked but not sure if it's allowed, thanks!

2. ## Re: Induction

Originally Posted by pikachu975
http://prntscr.com/fqo97b

For this, the marking guidelines says n=1,2,3 is obviously true so they prove base case n = 4
They assume true for n = k for k>=5
Prove true for n = k + 1

Would it be alright to do base case as n = 1
Assume true for n = k, n = k+1, n = k+2
Then prove true for n = k + 3
I did this and it worked but not sure if it's allowed, thanks!
$\noindent You should do (remark on) terms n = 1, 2, 3 separately and use n = 4 as the base case, because the 1-3 terms are just generally arbitrarily given (initial conditions) and don't form part of the sequence that gets forced by the recurrence relation, so it could have been that one of those first three terms was given as bigger than 2^n, and then the result wouldn't hold.$

$\noindent In other words, when you did the inductive step, you probably made use of the given recurrence relation, but that only holds if n\geq 4, which means you actually assumed n is at least 4 when doing the inductive step. So cases of n < 4 must all be checked separately and then you use actual induction for n \geq 4 only (so n=4 becomes the base case for this induction).$

3. ## Re: Induction

Originally Posted by InteGrand
$\noindent You should do (remark on) terms n = 1, 2, 3 separately and use n = 4 as the base case, because the 1-3 terms are just generally arbitrarily given (initial conditions) and don't form part of the sequence that gets forced by the recurrence relation, so it could have been that one of those first three terms was given as bigger than 2^n, and then the result wouldn't hold.$

$\noindent In other words, when you did the inductive step, you probably made use of the given recurrence relation, but that only holds if n\geq 4, which means you actually assumed n is at least 4 when doing the inductive step. So cases of n < 4 must all be checked separately and then you use actual induction for n \geq 4 only (so n=4 becomes the base case for this induction).$
Thanks for the detailed response, would it be alright to use my method or is it compulsory to make the base case n = 4 and go from there?

4. ## Re: Induction

Originally Posted by pikachu975
Thanks for the detailed response, would it be alright to use my method or is it compulsory to make the base case n = 4 and go from there?
Must do n = 4 as base case and go from there (after having verified n = 1, 2, 3).

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•