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.