Proving 13|4^(2n+1)+3^(n+2) for Positive Integers

[CartoonKid]

How to prove 13|4^(2n+1)+3^(n+2) for any positive integer?

 

[mathman]

Use induction. For n=0, the dividend is is 4+3²=13. In general:
Let a(n)=4²ⁿ⁺¹
b(n)=3ⁿ⁺²

Assume a(n)+b(n) divisible by 13.
a(n+1)=16a(n), b(n+1)=3b(n)
a(n+1)+b(n+1)=13a(n)+3(a(n)+b(n)), which is obviously divisible by 13.

 

[robert Ihnot]

It happens to be that 3==4^2 Mod 13. So the equation can be written as

4^(2n+1)+4^(2n+4) = (4^2n+1)(1+64)=(4^2n+1)(5*13)==0 Mod 13.

 

[CartoonKid]

thanks for the solution. here is another one. how to prove that for every positive integer n, 8|(5^n)+[2*3^(n-1)]+1? I am really struggling with proof. Is there any advice for me? Thanks in advance.

 

[CartoonKid]

It happens to be that 3==4^2 Mod 13. So the equation can be written as

4^(2n+1)+4^(2n+4) = (4^2n+1)(1+64)=(4^2n+1)(5*13)==0 Mod 13.

i haven't study mod before. can you explain to me how to use mod? or recommend some useful websites for reference. thanks.

 

[Gokul43201]

Any book on the Basics of Number Theory will cover modular arithmetic. If you have access to a library, I suggest you pick up something like Burton's Elementary Number Theory.

As for your second question, have you tried using induction, just the way mathman did it for the first problem ? That is the least you can do, before asking help on a question that is of the same type as your previous one.

 

[CartoonKid]

I have tried but halfway through I don't know how to continue.

this is the step where i don't know how to continue:
P(n+1): 2[(5^n)-1]+3[(5^n)+2*3^(n-1)+1]

Please give me some guide here. Thanks

 

[TenaliRaman]

P(n+1): 2[(5^n)-1]+3[(5^n)+2*3^(n-1)+1]
Look at the second part
[(5^n)+2*3^(n-1)+1]
Doesn't this look familiar ... isn't it your P(n) which u have assumed to be true?

now look at the first part,
[(5^n)-1]
can this not be factorised as,
4(5^n-1-...(+/-)1)
so 2*[(5^n)-1]
=8(5^n-1-...(+/-)1)

-- AI

 

[Gokul43201]

Tenali, that's nice.

I was going to suggest a similar approach, but less intuitive and more cumbersome. Let me show what I mean, anyway.

Here's a method :

Let P(n) : t(n) = 8k
Need to show P(n+1) is true given P(n), where P(n+1) : t(n+1) = 8k'

Start by writing t(n+1) = a*t(n) + s(n) = a*8k + s(n) = 8m + s(n). This may be done in several ways; find the one which makes s(n) simple.

Now you simply have to show that s(n) = 8p, say, and that's it. This can be done either directly (through factorization, such as Tenali has shown) or again inductively.

Let me demonstrate the only difference between my suggested method and Tenali's solution above.

Following the procedure as described, we have s(n) = 5^n - 1, and want to show that this is of the form 4p'. One way (the nicer one) of doing this is shown above. The stupid man's (my) way of doing it is as follows :

s(1) = 4, and s(n) = 4p = 5^n - 1, say. Or, 4p + 1 = 5^n

s(n+1) = 5^(n+1) - 1 = 5*5^n - 1 = 5*(4p+1) - 1 = 20p + 4 = 4p'

That was pretty straightforward. Not clever, but it works.

 

[CartoonKid]

First of all, thanks Tenali and Goku for giving me the solution. In fact, it took me some time to digest the solution. However, I still have some questions here.

Tenali, I am not very clear of the way you factorised (5^n)-1. Is it like this?
{4*[5^(n-1)]+4*[5^(n-2)]+...+4[5^1]+4[5^0]}-1
Then, you factorised 4 from the series.
Is it how you deal with the 5^n part? Why there is (+/-)1 at the back? In my way of factorisation, there is still left -1 at the back?

I hope you can help me further. Thanks.

 

[TenaliRaman]

(I am too lazy to do latex but i think situation demands it right now)

CartoonKid,
In general,
$$a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + ... + b^{n-1})$$
(...
CartoonKid : hey u put all plus signs now and u had put negative signs before ... which is right??
TenaliRaman : err ... ummm u see it was pretty late last night and i was dreaming abt this princess who comes in a horse and picks me up and then also buys me a G5 and P4 HT machines .. so it all err umm u get it right!
...)

How to go abt showing this?
1>Using modular arithmetic : we'll skip this as u are not introduced to this method yet
2>How abt Geometric progression ? ofcourse
we know that,
1+x+x^2+x^3+...+x^n = (1-x^n)/(1-x)
put x = b/a and simplify and see what u get ...

There are many more ways but i will let u discover it ...

-- AI

 

[CartoonKid]

(I am too lazy to do latex but i think situation demands it right now)

CartoonKid,
In general,
$$a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + ... + b^{n-1})$$
(...
CartoonKid : hey u put all plus signs now and u had put negative signs before ... which is right??
TenaliRaman : err ... ummm u see it was pretty late last night and i was dreaming abt this princess who comes in a horse and picks me up and then also buys me a G5 and P4 HT machines .. so it all err umm u get it right!
...)

How to go abt showing this?
1>Using modular arithmetic : we'll skip this as u are not introduced to this method yet
2>How abt Geometric progression ? ofcourse
we know that,
1+x+x^2+x^3+...+x^n = (1-x^n)/(1-x)
put x = b/a and simplify and see what u get ...

There are many more ways but i will let u discover it ...

-- AI

Haha. I like your explanation. Thanks a thousand.