Math Is Fun Forum

JohnD

Member

Registered: 2009-05-19

Posts: 1

Mathematical Induction & Recurrence

Hi,

I'm currently studying at Uni and our topic has now been started on.  I haven't done any serious maths for a long, long time and I am struggling quite badly to understand what I am trying to do.  I've read and re-read all my material but nothing is click, at the moment it is like another language to me and since this is the last part of my assignments this year I don't want to bring to down my average too much.  So I was wondering if you could help me figure out this problem.

U(0) = 8
U(i)=17+2 × U(i− 1) (i>0)

Question:

For an integer i,with i≥ 0, U(i) is defined by the recurrence system in part (a)(iii) see above, and F(i) is defined by the formula F(i)= 25 × 2i − 17. Prove by mathematical induction that U(i)= F(i) (for all integers iwith i≥ 0).

I'll be honest, I have no idea where to start.

Any help would be grateful.

Thanks
John.

Last edited by JohnD (2009-05-20 06:27:28)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Mathematical Induction & Recurrence

Hi,

U(0) = 8
U(i)=17+2 × U(i− 1) (i>0)

Question:

For an integer i,with i≥ 0, U(i) is defined by the recurrence system in part (a)(iii) see above, and F(i) is defined by the formula F(i)= 25 × 2i − 17. Prove by mathematical induction that U(i)= F(i) (for all integers iwith i≥ 0).

Hi John;
I can't prove that because that is the wrong answer. The correct answer is

from there we have 2 ways of proving it:

1) solving the recurrence to produce that answer.
2) by induction

To prove by induction:

Lets assume that F(i) is true.

This is our assertion:

the base case is true.

The inductive step is:

Take the original recursion

plug our assertion into the right hand side for U(i).

This is the same as the inductive step. The proof is done.

Last edited by bobbym (2009-05-24 04:53:54)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.