induction please help

santamariaah · New Member Offline Joined: 05 Nov 2009 Posts: 1

prove that for all n>0 , 4^n + 15n - 1 is divisible by 9/multiple of 9

I tried:

(4^n + 15n - 1)/9 = k = 4^n + 15n - 1 = 9k

4^n+1 + 60n - 4 = 36k

stuck now

thanks!!

**Posted:** Thu Nov 05, 2009 8:00 pm

kunny

See here.http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1511897&search_id=1679993286#1511897

**Posted:** Thu Nov 05, 2009 8:49 pm

_________________
Today's calculation of Integral Digest

mavropnevma

$4^n + 15n - 1$ computed in $n=1$ yields $18$ . Assume divisible by $9$ until $n$ .

Now $4^{n+1} + 15(n+1) - 1 = 4(4^n + 15n - 1) - 9(5n - 2)$ and all is clear.

**Posted:** Thu Nov 05, 2009 11:00 pm

_________________
Listen to REMBETIKA for decoding the handle.

aadil

$4^3 =1 mod 9$ so when 3 divides n the expression is divisible by 9. similarly when n is $1$ or $2 mod 3$ it is divisible by 9

**Posted:** Fri Nov 06, 2009 3:34 am

_________________
Rotfl

quantum mechanics-the gem of physics

Dr Sonnhard Graubner

hello, since $4^3\equiv 1 \mod 9$ we have to consider three cases
a) $n=3k$
b) $n=3k+1$
c) $n=3k+2$
from here we got
a) $4^{3k}+15\cdot3k-1\equiv 1+0-1\equiv 0 \mod 9$
b) $4^{3k+1}+15(3k+1)-1\equiv (4^3)^{k}\cdot4+45k+15-1\equiv18\equiv 0 \mod 9$
c) $4^{3k+2}+15(3k+2)-1\equiv (4^3)^{k}\cdot16+45k\cdot30-1\equiv45\equiv 0\mod 9$
Sonnhard.

**Posted:** Sat Nov 07, 2009 2:01 am

rowan

case $n=1$
$4^{1}+15(1)-1=18$

assuming true up to $n$

$4^{n+1}+15(n+1)-1$
$3*4^{n}+15+(4^n+15n-1)$
$3(4^{n}+5)+(4^n+15n-1)$

and then because $4^n\equiv 1\mod 3$ and $5\equiv 2\mod 3$
so $4^n+5 \equiv 0\mod 3$ and we are done.

**Posted:** Mon Nov 09, 2009 12:14 pm