RECURSION AND MATHEMATICAL INDUCTION

Question

You are given the sequence defined as follows

a _n = 3 a _n-1 +n , ∀ n ≥ 2

a ₁ = 1

Use iteration to guess an explicit formula for a _n and then use mathematical induction to

prove the correctness of the formula guessed.

Answer 1

This was what I was thinking only after I started writing down a few terms:

a₂ = 3(1) + 2 = 3(1) + 2

a₃ = 3(3 + 2) = 3²(1) + 2(3) + 3

a₄ = 3(3² + 2(3) + 3) +4 = 3³(1) + 3²(2) + 3(3) + 4

a₅ = 3[3³(1) + 3²(2) + 3(3) + 4] = 3⁴(1) + 3³(2) + 3²(3) + 3(4) + 5

I didn't start writing the terms like that, but when trying to look for a pattern, it helped.

From the above, my guess was that for any n ≥ 2 :

a_{n =} 1*3^n-1 + 2*3^n-2 + ... (n-1)*3 + n or just

_n

a_n = ∑ j*3^(n-j) (Is there an easy way to type a summation with the limits using Wyzant?)

^j=1

check if it works for n=2

₂

a₂ = ∑ j * 3^(n-j) = 1*3^(2-1) + 2*3^(2-2) = 3 + 2 = 5 Works for n = 2

^j=1

_k

Assume true for any n = k , so a_k = ∑ j*3^(k-j) is true by our assumption.

^{j = 1}

_k+1

Show true for n = k + 1 i.e. show a_k+1 = ∑ j*3^{(k+1) - j}

^j=1

By definition of the sequence, we were given:

a_k+1 = 3a_k + (k +1) ;

using our assumption

_k

a_k+1 = 3[ ∑ j * 3^(k-j)] +(k+1)

j=1

I will write out some terms of the summation to see if it helps

a_k+1 = 3[ 1*3^k-1 + 2*3^k-2 + ...(k-1)*3 + k ] + (k + 1)

Distribute the 3

a_k+1 = 1*3^k + 2*3^k-1 + ... (k-1)*3² + k*3 + (k+1)

But this is the same as

_{k +1}

a_{k+1 =} ∑ j*3^{(k+1) - j} (Please check if you agree)

_{j = 1}

which is what we wanted to show.

Note: Yes, you can use summation formulas, or possibly even derive using a double summation, a closed

n

form of ∑ j*3^{(n - j)}

j = k

Maybe the answer for this question requires this, but I wasn't nearly as interested in doing that , and I think the induction is more natural this way.

Answer 2

Borrowing From Eduardo S. 

a₁ = 1

a₂ = 3(1) + 2 = 3(1) + 2

a₃ = 3(3 + 2) = 3²(1) + 2(3) + 3

a₄ = 3(3² + 2(3) + 3) +4 = 3³(1) + 3²(2) + 3(3) + 4

a₅ = 3[3³(1) + 3²(2) + 3(3) + 4] = 3⁴(1) + 3³(2) + 3²(3) + 3(4) + 5

There is a pattern emerging , and therefore we suggest a_n

a_n = 3^n-1 + 2· 3^n-2 + 3 ·3^n-3 + 4·3^n-4 + 5·3^n-5 +····+ (n-2)·3² +(n-1)·3 +n =

3^n-1 + 3^n-2 + 3^n-3 + 3^n-4 + 3^n-5 +····+ 3² +·3 +1------------------------------> = ( 3ⁿ − 1) / 2

3^n-2 + 3^n-3 +3^n-4 + 3^n-5 +····+ 3² + 3 +1------------------------------> = ( 3^n-1 − 1) / 2

3^n-3 +3^n-4 + 3^n-5 +····+ 3² + 3 + 1-------------------------------> = ( 3^n-2 − 1) / 2

3^n-4 + 3^n-5 +····+ 3² + 3 + 1-------------------------------> = ( 3^n-3 − 1) / 2

•

•

•

3² + 3 + 1-------------------------------> = ( 3³ − 1) / 2

3 + 1-------------------------------> = ( 3² − 1) / 2

1--------------------------------> = ( 3 − 1) / 2

____________________________________________________________________________

a_n = ( 3ⁿ − 1) / 2 + ( 3^n-1 − 1) / 2 + ( 3^n-2 − 1) / 2 + ····+ ( 3³ − 1) / 2 + ( 3² − 1) / 2 + ( 3 − 1) / 2 =

= (1/2) [ 3ⁿ + 3^n-1 + 3^n-2 + 3^n-3 + ·····+ 3⁴ + 3³ + 3² + 3 + 1−n −1]

= ( 3ⁿ⁺¹ − 1) / 4 − ( n +1 ) /2

( 3ⁿ⁺¹ ) /4 − n / 2 −3 / 4 ∀ n ≥ 1

Now let us use mathematical induction to test the correctness of the obtained formula.

A. For n = 1 a₁ = 9/4 - 1/2 - 3/4 = 1 TRUE

B. Assuming that a _k = ( 3^k+1 ) /4 − k / 2 −3 / 4

we must prove that a _k+1 = ( 3^k+2 ) /4 −( k +1 ) / 2 −3 / 4

PROOF

From the recursive formula we have a _k+1 = 3 a _k + k + 1.

Also from the inductive hypothesis we have that a _k = ( 3^k+1 ) /4 − k / 2 −3 / 4

then a _k+1 = 3 a _k + k + 1.= 3 [ ( 3^k+1 ) /4 − k / 2 −3 / 4 ] + k + 1.=

= ( 3^k+2 ) /4 −3k /2 −9/4 + k +1

= ( 3^k+2 ) /4 −3k /2 + k +1 −9/4

= ( 3^k+2 ) /4 −3k /2 +2 k / 2 +1 −9/4

= ( 3^k+2 ) /4 −k /2 −5/4

= ( 3^k+2 ) /4 −k /2 −2/4 −3/4

= ( 3^k+2 ) /4 −( k +1 ) / 2 −3 / 4

Answer 3

a₁=1

a₂=3(1)+2=5

a₃=3(5)+3=18

a₄=3(18)+4=58

a₅=3(58)+5=178

...

a_n= (-1/2)n +(3/4)(3ⁿ-1)

Good luck on trying to find that explicit formula based on iteration. Not sure how you would do that. I looked up linear homogeneous and non-homogeneous recurrence to figure out that formula.

This is confirmation that the explicit formula seems to be correct:

desmos.com/calculator/9kipg8mfb3

To use mathematical induction to prove that it works for all n>=2:

1) prove that it works for n = 2 (it works for n=1 too).

a₂=(-1/2)2 +(3/4)(3²-1) = -1 +(3/4)(8) = -1 + 6 = 5.

2) Assume the formula works for k and show that it must work for k +1.

Assumption:

a_k=(-1/2)k +(3/4) (3^k-1)

Show that it works for a_k+1.

We know a_k+1= 3(a_k) + (k+1)

Therefore by assumption:

A) a_k+1= 3[(-1/2)k+(3/4)(3^k-1)]+(k+1) [this is the recursive definition for a_k+1 based on a_k]

The goal is to transform that equation into what a_k+1 looks like if (k+1) is substituted into the explicit formula for a_n.

That would look like this:

B) a_k+1 = (-1/2)(k+1) + (3/4)(3^k+1-1) [this is a_k+1 using the explicit formula found by "iteration"]

Transforming A into B is left to the reader :)