Is f(n) = 4^n + 6n - 1 Divisible by 9 for All Positive Integers n?

[synkk]

Prove that f(n) = 4^n + 6n - 1 is divisible by 9 for all positive integers of n.

I've proved this by considering that f(k) is divisible by 9, i.e f(k) = 4^k + 6k -1 = 9m where m is some integer. Rearranging to give 4^k = 9m - 4k + 1 and then considering f(k+1) = 4^(k+1) + 6(k+1) - 1 then substituting 4^k and showing it is divisible by 9, which works.

I've been trying to do it another way i.e by considering f(k+1) - f(k), doing so I get

f(k+1) -f(k) = 4^{k+1} + 6k + 6 -1 -4^k -6k + 1
and then going on to get f(k+1) -f(k)= 3(4^k) + 6

however I'm stuck here, I can obviously see that this is divisible by 9, but how can I show it?

EDIT: Similarly how do I show that 120(2^(4k)) + 78(3^(3k)) is divisible by 11?

 

[szynkasz]

Hint:
4^k=(3+1)^k

 

[synkk]

Hint:
4^k=(3+1)^k

I still can't seem to get it, I've expanded with the binomial expansion.

 

[HallsofIvy]

First, of course, f(0)= 4^0+ 6(0)- 1= 0= 9(0).

Now assume that, for some k, f(k)= 4^k+ 6k- 1 is a multiple of 9 and look at
f(k+ 1)= 4^{k+1}+ 6(k+ 1)- 1= 4(4^k)+ 6k+ 5.

Looking at that 4 times 4^k, it occcurs to me to write 6k= 24k- 18k= 4(6k)- 18k and 5= -4+ 9.

Do you see why?
f(k+1)= 4^{k+1}- 6(k+1)- 1= 4(4^k+ 6k- 1)- 18k+ 9

 

[synkk]

First, of course, f(0)= 4^0+ 6(0)- 1= 0= 9(0).

Now assume that, for some k, f(k)= 4^k+ 6k- 1 and look at
f(k+ 1)= 4^{k+1}+ 6(k+ 1)- 1= 4(4^k)+ 6k+ 5.

Looking at that 4 times 4^k, it occcurs to me to write 6k= 24k- 18k= 4(6k)- 18k and 5= -4+ 9.

Do you see why?
f(k+1)= 4^{k+1}- 6(k+1)- 1= 4(4^k+ 6k- 1)- 18k+ 9

woah that's pretty smart, though I don't particularly think I could get to that step on my own.

 

[szynkasz]

I still can't seem to get it, I've expanded with the binomial expansion.

3\cdot (3+1)^k+6=3\cdot\sum_{m=0}^k {k\choose m}3^m+6=3\cdot \sum_{m=1}^k {k\choose m}3^m+3+6=9\cdot \sum_{m=1}^k {k\choose m}3^{m-1}+9

 

[synkk]

3\cdot (3+1)^k+6=3\cdot\sum_{m=0}^k {k\choose m}3^m+6=3\cdot \sum_{m=1}^k {k\choose m}3^m+3+6=9\cdot \sum_{m=1}^k {k\choose m}3^{m-1}+9

I'm not really familiar on your notation, here's how I expanded:

3(3^k + \displaystyle \binom{k}{1}3^{k-1} + \displaystyle \binom{k}{2}3^{k-2}+...)

 

[Mentallic]

I'm not really familiar on your notation, here's how I expanded:

3(3^k + \displaystyle \binom{k}{1}3^{k-1} + \displaystyle \binom{k}{2}3^{k-2}+...)

Right, and what happens at the end of that expansion? It comes down to,

3(4^k)
=3(3+1)^k
=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} + ...+\displaystyle \binom{k}{k-1}3+1\right)
=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k-1}3\right)+3

Can you carry on from here?

 

[synkk]

Right, and what happens at the end of that expansion? It comes down to,

3(4^k)
=3(3+1)^k
=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} + ...+\displaystyle \binom{k}{k-1}3+1\right)
=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k-1}3\right)+3

Can you carry on from here?

No, I can't.

I thought the last term would be =3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k}3\right)+3

I don't know how to proceed either way.

 

[eumyang]

No, I can't.

I thought the last term would be =3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k}3\right)+3

No, it's not. Mentallic had it right.
=3(4)^k
=3(3+1)^k
I'll insert a step here:
=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} + ...+\displaystyle \binom{k}{k-1}3^1+\displaystyle \binom{k}{k}3^0\right)
=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} + ...+\displaystyle \binom{k}{k-1}3+1\right)
=3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k-1}3\right)+3

 

[Mentallic]

No, I can't.

I thought the last term would be =3\left(3^k + \displaystyle \binom{k}{1}3^{k-1} +...+\displaystyle \binom{k}{k}3\right)+3

I don't know how to proceed either way.

The binomial expansion is as follows:

(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^{n-k}b^k

Or if we express that sum the long way, we get

\binom{n}{0}a^{n-0}b^0+\binom{n}{1}a^{n-1}b^1+\binom{n}{2}a^{n-2}b^2+ ... +\binom{n}{n-2}a^{n-(n-2)}b^{n-2}+\binom{n}{n-1}a^{n-(n-1)}b^{n-1}+\binom{n}{n}a^{n-n}b^{n}

Now, there's a lot of simplifications we can do on the very left and right-hand sides.
\binom{n}{0}=\binom{n}{n}=1
a^{n-n}=a^0=b^0=1
a^{n-(n-k)}=a^k

After applying all these simplifications, the binomial expansion becomes
a^n+\binom{n}{1}a^{n-1}b+\binom{n}{2}a^{n-2}b^2+ ... +\binom{n}{n-2}a^2b^{n-2}+\binom{n}{n-1} ab^{n-1}+b^n

Applying a=3 and b=1 gives us something much simpler because all of the b terms essentially vanish since b^k=1.

3^n+\binom{n}{1} 3^{n-1}+\binom{n}{2}3^{n-2}+ ... +\binom{n}{n-2}3^2+\binom{n}{n-1}3+1

Now multiply the whole expression by 3, and remove the +1 term from the sum out of the brackets.