Evidence of recurrence

To evidence by recurrence, follow the steps below exactly as shown, in the given order:

Step # 1:

Show this is true for n = 1, n = 2…

Step # 2:

Suppose that this is true for n = k

Step # 3:

To prove this is true for n = k + 1

Notes the explanations on evidence by recurrence and important:

Step # 1, you try to show that this is true for specific values. You are free to do this test with a single value or fifty values of your choice or more.

However, showing this is true for the values of one million or more does not prove it will be true for all values. It is a very important observation!

In step # 2, since you have already shown that this is true for one or more values, it is logical to assume or assumes that this is true for n = k or generally.

We usually use the asumption that here we complement or prove step # 3

Step # 3, finally show you that it is true for all values. Note that this step # 2 does not show that this is true for all values.

Example:

Show that for any n, 2 + 4 + 6 +… + 2n = n (n + 1)

Step # 1:

Display the equation is true for n = 1, n = 2…

There is a pitfall to avoid here.

n = 1 means the first value of the expression on the left side. In this case 2

n = 2 means the first two values of the expression on the left side. In this case 2 + 4.

n = 3 means the first three values in the expression on the left side. In this case 2 + 4 + 6

Thus, showing the equation 2 + 4 + 6 +… + 2n = n (n + 1) is true for n = 4 means we need to show that 2 + 4 + 6 + 8 = 4 (4 + 1)

2 + 4 + 6 + 8 = 6 + 6 + 8 = 12 + 8 = 20 and 4 (4 + 1) = 4 × 5 = 20

Since the left side is equal to the right (20 = 20), step # 1 is done. It is not necessary to choose other values that you could do it just for fun and to prove to yourself that it will work for other values.

Step # 2:

Assume that the equation is true for n = k

Just replace n by k.

2 + 4 + 6 +… + 2 k = k (k + 1)

Step # 3:

To prove the equation is true for n = k + 1

It is the most difficult part of the evidence by recurrence. Things can get really hard here. Step in this well problem!

At this stage, you need to write what it means for the equation be true for n = k + 1

Be careful! Just because you wrote what means does not mean that you have proved it. There is another pitfall to avoid when you work on a proof by recurrence.

What this means:

After replacing k by k + 1, you get:

2 + 4 + 6 +… + 2 × (k + 1) = k + 1 (k + 1 + 1)

2 + 4 + 6 +… + 2 × (k + 1) = k + 1 (k + 2)

2 + 4 + 6 + … + 2 × ( k + 1) = ( k + 1 ) × ( k + 2)

We will give you a summary because you may have lost tract of what we are trying to do here.

We do not prove anything yet. The equation 2 + 4 + 6 +… + 2 × (k + 1) = (k + 1) × (k + 2) is what it means for the equation be true for n = k + 1

We are now ready to complete the proof by recurrence using the hypothesis in step no. 2.

on the assumption, 2 + 4 + 6 +… + 2 k = k (k + 1)

Say to yourself, “that the next term is seeking as”?

Since the latter term is now 2 k, the next term should be 2 × (k + 1)

Add 2 × (k + 1) on both sides of the hypothesis

2 + 4 + 6 +… + 2 k + 2 × (k + 1) = k (k + 1) + 2 × (k + 1)

= k2 + k + 2 k + 2.

= k2 + 3 k + 2.

Since 2 = 1 × 2 and 1 + 2 = 3,

k2 + 3k + 2 = ( k + 1) × ( k + 2)

Therefore, 2 + 4 + 6 +… + 2 k + 2 × (k + 1) = (k + 1) × (k + 2) and evidence of recurrence is complete!

The above is a solid and well explained by recurrence. Although study!

Page copy protected against web site content infringement by Copyscape

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s