Harder Induction (1 Viewer)

nofate · Mar 17, 2012

I'm having a problem regarding a specific harder induction question. I'm not that great at the harder induction (I've only attempted one or two), so it may be an easy solution.

Question: For a sequence of numbers $a_{1} = 2, a_{2} = 3$ and $a_{n} = 3a_{n-1} - 2a_{n-2}$ for all integers $n \ge 3$ . Prove by mathematical induction that $a_{n} = 2^{n-1} + 1$ .

In the solution, I get up to the part where $a_{k + 1} = 3(2^{k-1} + 1) - 2a_{k-1}$ , but I have no idea to find the value of $a_{k-1}$ . Can anyone help?

SpiralFlex · Mar 17, 2012

Let $S(n)$ be true for all integers $n\leq k$

Then

$a_{n}=2^{k-1}+1 \; $for$ \; n=1,2....k-1,k$

$a_{k-1}=2^{k-2}+1$

Now back to your last step.

$S(k+1)=3(2^{k-1}+1)-2(2^{k-2}+1)$

$=3*2^{k-1}+3-2^{k-1}-2$

$\therefore S(k+1)=2^{k}+1$

$Hence the statement is true for n=k+1.$

Posted on iPhone may contain traces of mistakes need to go out now bye. Penguin up!

Carrotsticks · Mar 17, 2012

I think I posted a faster way of doing these kinds of questions (linear homogenous recurrence relations) somewhere on the forum.

Here's an article showing you how to do them an alternative (and much faster) way: http://pages.pacificcoast.net/~cazelais/222/rec.pdf

But most questions in exams will unfortunately ask you to 'prove' it by induction.

SpiralFlex · Mar 17, 2012

They will always put by induction to stop the above from happening.

bleakarcher · Mar 17, 2012

^ I dont think many people would know about the method Carrotsticks taught us though.

IamBread · Mar 17, 2012

SpiralFlex said:
$a_{n}=2^{k-1}+1 \; $for$ \; n=1,2....k-1,k$

Posted on iPhone may contain traces of mistakes need to go out now bye. Penguin up!

It did

You put in k, not n lol.
$a_{n}=2^{n-1}+1 \; $for$ \; n=1,2....k-1,k$

nofate · Mar 17, 2012

Ah, I missed out on one step. Thanks heaps

Make a Difference – Donate to Bored of Studies!

Harder Induction (1 Viewer)

nofate

Member

SpiralFlex

Well-Known Member

Carrotsticks

Retired

SpiralFlex

Well-Known Member

bleakarcher

Active Member

IamBread

Member

nofate

Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)