Expert: Paul Klarreich - 5/27/2007

Question
1. Let the sequence {an} be defined recursively by:
an=6a(n-1)-9a(n-2), a1=0,a2=9.
Use Strong induction to prove that an=3^n(n-1).
note: the an is written like, big a then small n. so 6a then small n-1 next to it.

2. (a) apply the Euclidean algorithim to find gcd(966,320), show your working.
(b) Go on to find integers x,y such that 966x+320y=gcd(966,320).

Answer
Questioner:   Scott
Category:  Advanced Math
 
Subject:  algebra
Question:  1. Let the sequence {an} be defined recursively by:
an=6a(n-1)-9a(n-2), a1=0,a2=9.
Use Strong induction to prove that an=3^n(n-1).
note: the an is written like, big a then small n. so 6a then small n-1 next to it.

2. (a) apply the Euclidean algorithim to find gcd(966,320), show your working.
(b) Go on to find integers x,y such that 966x+320y=gcd(966,320).
.............................................
Hi, Scott,

[see advisory at the end]

You have the definition, as best I can make out, that:

a[n] = 6a[n-1] - 9a[n-2]

Now as I recall, there are two forms of induction to prove a statement S[n] for all n:

First form:

Base case: prove S[1] (or  S[0], or whatever is the base case.)
Then prove that for any n, S[n] --> S[n+1].
(i.e. prove S[n+1] from the knowledge that S[n] is true.)

Second form:

Base case as above.
Then prove that for any n,  S[1]..S[n] --> S[n+1]

(i.e. prove S[n+1] from the knowledge that S[1]..S[n] are all true.)

The second is the one called Strong Induction.  [I always had a little trouble with the terminology, but I looked it up.  The rest of the world seems to think this is correct, so who am I to argue?]  

Why will you need Strong Induction for this?  Probably because your proof for S[n+1] will require more than just knowledge of  S[n].

So here is your statement S[n]:

If  a[n] = 6a[n-1] - 9a[n-2],  with  a[1] = 0,  a[2] = 9, then for all n,  a[n] =  3^n(n-1).

Base case(s):
a[1] = 3^1(1-1) = 3(0) = 0
a[2] = 3^2(2-1) = 9(1) = 9
Good.
. . . . . . . . .
Now assume that for   k = 1..n,  a[k] = 3^k(k - 1)

Prove that  a[n+1] = 3^(n+1) ((n+1) - 1) = 3^(n+1)(n)

Proof: The recurrence says:  a[n+1] = 6a[n] - 9a[n-1]

Now use the inductive assumptions (yes, assumptions, plural.  This is why we need the strong form):

a[n]    = 3^n (n - 1)
a[n-1]  = 3^(n-1) (n - 2)

a[n+1] = 6(3^n (n - 1)  ) - 9( 3^(n-1) (n - 2) )

Now a little algebra:

a[n+1] = 2*3(3^n (n - 1)  ) - 3^2( 3^(n-1) (n - 2) )

a[n+1] = 2*3^(n+1) (n - 1) - 3^(n+1) (n - 2)

a[n+1] = 3^(n+1)(2(n - 1) - (n - 2))

a[n+1] = 3^(n+1)( 2n - 2 - n + 2 )

a[n+1] = 3^(n+1)( n )

THAT'S IT!  That's what you were supposed to prove.
.....................................................
2. (a) apply the Euclidean algorithim to find gcd(966,320), show your working.
(b) Go on to find integers x,y such that 966x+320y=gcd(966,320).

As I recall the E.A. it works like this:

Divide  966 by 320, using the division algorithm.
320 into 966  goes  3 times, with a remainder of 6
Division algorithm says:  966 = 3 * 320 + 6
So the GCD will divide 966, 320, AND 6.

Divide again:
6 into  320 gpes  53 times, with a remainder of 2
Division algorithm says:  320 = 53 * 6 + 2
So the GCD divides 320, 6, AND  2.

Divide again:

2 into  6 goes  3 times with a remainder of 0.
Division algorithm says:  6 = 3 * 2 + 0

That's it.  When you get a remainder of zero, the previous remainder is your GCD, in this case 2.
. . . . . . . . . .

(b) Go on to find integers x,y such that 966x+320y=gcd(966,320).

Comment:  Since  966 and 320 are both much bigger than 2, obviously one of x and y will have to be negative.

I think GO ON means to use the above division arithmetic to find the values of x and y.  Like this:

D.A. says:  966 = 3 * 320 + 6, or  6 = 966 - 3 * 320
D.A. says:  320 = 53 * 6 + 2,  or  2 = 320 - 53 * 6

There's your '2' that you want.

2 = 320 - 53 * 6
AND
6 = 966 - 3 * 320

Substitute for that six:

2 = 320 - 53 * (966 - 3 * 320)

Remove parentheses and do some simplifying:

2 = 320 - 53 * 966 + 159 * 320
2 =     - 53 * 966 + 160 * 320

OK, then.  There's your x and y:  x = -53, y = 160.
.....................................................
Advisory:

I have added an instruction to my profile, asking users NOT to send me questions that are also sent to someone else.  If you are asking an opinion, like 'what is the best calculus book', that's one thing -- ask three mathematicians about that and you get four different answers.
But you are asking for a solution, and you are unlikely to get different solutions, just the same one more than once, which makes it a waste of time for someone.  Further, you use up the 'question limit' for two people which is not fair.

You did it once recently.  That was before I objected, so I have no dispute with you, but please don't repeat it.  If I can't answer a question you send me, I'll try to say so quickly, and I can send it to the question pool, where anyone can answer it.