My Math Forum proof recurrence

 Number Theory Number Theory Math Forum

 November 22nd, 2010, 11:29 AM #1 Member   Joined: Oct 2010 Posts: 30 Thanks: 0 proof recurrence could someone show me how to prove this please The sequence u1,u2,u3,... is defined recursively by the rules that u1 =6,u2 =9, and for n ? 3, un = 3u n?1+18u n?2. Prove that un is a multiple of 3^n for all n ? N
 November 22nd, 2010, 11:42 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: proof recurrence Notice that the coefficient of un-1 is divisible by 3 and the coefficient of un-2 is divisible by 3^2: $3u_{n-1}+18u_{n-2}$.
November 22nd, 2010, 09:49 PM   #3
Math Team

Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 408

Re: proof recurrence

Hello, riotsandravess!

Quote:
 Could someone show me how to prove this please? $\text{The sequence }u_1,\,u_2,\,u_3\,\cdots \text{ is defined recursively by: }\:u_1= 6,\;u_2 =9,\;u_n \:=\: 3u_{n-1}\,+\,18u_{n-2}$ $\text{Prove that }u_n\text{ is a multiple of }3^n\text{ for all }n\,\in\,N.$

We can find the closed form for the sequence, but it takes a bit of work . . .

$\text{We have: }\;u_n \,-\,3u_{n-1}\,-\,18u_{n-2} \;=\;0$

$\text{Let: }\,X^n \:=\:u_n$

$\text{Then we have: }\:X^n\,-\,3X^{n-1}\,-\,18X^{n-2} \:=\:0$

$\text{Divide by }X^{n-2}:\;\;X^2\,-\,3X\,-\,18 \:=\:0 \;\;\;\Rightarrow\;\;\;(X\,-\,6)(X\,+\,3) \:=\:0$

[color=beige]. . [/color]$\text{Hence: }\:X \:=\:6,\:-3$

$\text{The generating function is of the form: }\:u(n) \;=\;A(6^n)\,+\,B(-3)^n$

$\text{Use the first two terms of the sequence to set up a system of equations.}$

[color=beige]. . [/color]$\begin{array}{ccccccccccccc} u(1) \,=\,6: &6A\,-\,3B=&6=&\Rightarrow=&2A\,-\,B=&2=&[1] \\ u(2)\,=\,9: &36a\,+\,9B=&9=&\Rightarrow=$

$\text{Add [1] and [2]: }\:6A \,=\,3\;\;\;\Rightarrow\;\;\;A \,=\,\frac{1}{2}$

$\text{Substitute into [1]: }\:1\,-\,B\:=\:2 \;\;\;\Rightarrow\;\;\;B\,=\,-1$

$\text{Hence, the generating function is: }\:u(n) \;=\;\frac{1}{2}(6^n)\,-\,(-3)^n$

$\text{Then: }\:u(n) \;=\;\frac{1}{2}(2^n)(3^n)\,-\,(-1)^n(3^n) \;=\;3^n\bigg[\frac{1}{2}(2^n)\,-\,(-1)^n\bigg] \;=\;3^n\bigg[2^{n-1}\,-\,(-1)^n\bigg]$

$\text{Therefore, }u_n\text{ is a multiple of }3^n\text{ for all }n\,\in\,N.$

 Tags proof, recurrence

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post ilikecereal Applied Math 1 February 28th, 2011 01:39 PM natkoza Real Analysis 2 December 6th, 2010 01:20 PM CarpeNoctum Computer Science 3 October 12th, 2010 02:08 PM Student 100 Computer Science 2 November 25th, 2008 05:52 AM nithins Number Theory 1 April 15th, 2007 03:08 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top