Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please hint me, I have two questions:

Prove by induction that:

1)

$$ {13}^n+7^n+19^n=39k,\,\, n\in\mathbb O$$

in which $\mathbb O$ is the set of odd natural numbers.

2)

$$ 5^{2n}+5^n+1=31t,~n\not=3k, $$ $n\in \mathbb N$

share|improve this question
3  
You may make the title more descriptive. –  B. S. Oct 11 '13 at 10:42
1  
Do you really need to prove the first by induction? Considering residues modulo $39$ is sufficient. –  Kieren MacMillan Oct 11 '13 at 10:45
    
what have you tried? –  Ma Ming Oct 11 '13 at 10:50
    
I need solve the both of them with induction but if you have another solution , please write it. I like different ways. –  Mohsen Oct 11 '13 at 11:01
add comment

3 Answers

With congruences instead of induction:

(1) You need to show that $13^n+7^n+19^n$ is divisible by both $3$ and $13$. This follows from $$13^n+7^n+19^n\equiv 1^n+1^n+1^n=3\equiv 0 \ ({\rm mod\ } 3),$$ $$13^n+7^n+19^n\equiv 0^n+7^n+(-7)^n\ ({\rm mod\ }13),$$ where the last expression is $=0$ since $n$ is odd.

(2) Here, I'd like to rewrite $$5^{2n}+5^n+1=(5^n)^0+(5^n)^1+(5^n)^2={(5^n)^3-1\over 5^n-1}={5^{3n}-1\over 5^n-1},$$ using the formula for geometric series (assuming $n\neq 0$). Note that $$5^{3n}-1=125^n-1\equiv 1^n-1=0\ ({\rm mod\ }31).$$ If $n$ is not divisible by $3$ then $n=3k+1$ or $n=3k+2$, and we have $$5^{3k+1}-1=5\cdot 125^k-1\equiv 5\cdot 1^k-1=4\ ({\rm mod\ }31),$$ $$5^{3k+2}-1=25\cdot 125^k-1\equiv 25\cdot 1^k-1=24\ ({\rm mod\ }31)$$ So $31$ divides the product $(5^{2n}+5^n+1)(5^n-1)=5^{3n}-1$, but not the factor $5^n-1$. Since $31$ is a prime number, it has to divide the other factor $5^{2n}+5^n+1$.

share|improve this answer
    
The last method resembles math.stackexchange.com/questions/515618/… –  lab bhattacharjee Oct 11 '13 at 13:35
    
very nice solution ! excellent ! :) –  average Oct 11 '13 at 13:56
    
Well done!!!!!! –  Mohsen Oct 11 '13 at 17:13
add comment

In the first one, you have to make two inductions.

For $n=1, 13^1+7^1+19^1 = 39 = 39k $ for $k=1 $

Assume the proposition is true for $n$, that is

$$ 13^n + 7^n + 19^n = 39k \qquad (1)$$ Let's check out what's gonna happen for $n+2$:

$$ 13^{n+2} + 7^{n+2} + 19 ^{n+2} $$ $$ = 13^n * 169 + 7^n * 49 + 19^n * 361$$ $$ = (39k-7^n - 19^n)*169 +7^n*49 + 19^n * 361 \qquad Got \,13^n from \,(1)$$ $$ = 39k*169 + 192 * 19^n - 120 * 7^n $$ (2)

It's clear that $39k*169$ is divisible by 39, let's make another induction for $192 * 19^n - 120 * 7^n$

For $n=1: \qquad 192 * 19^1 - 120 * 7^1 = 72*39$

Asuume $192 * 19^n - 120 * 7^n = 39t \qquad (3)$ and check out the situation for $n+2$

$$192*19^{n+2} - 120*7^{n+2} $$ $$=192*361*19^n - 120 * 49 * 7^n$$ $$=361 * (39t +120 * 7^n) - 120 *49*7^n \qquad Again, got \, 192*19^n from \,(3)$$ $$=361 * 39t + 120*7^n * (361-49)$$ $$= 361*39t + 120*7^n*8*39 \qquad As\, 361-49=8*39$$ $$= 39* (361t - 120*7^n*8) \qquad (4)$$

Plug $(4)$ into $(2)$ to show $$ 13^{n+2} + 7^{n+2} + 19 ^{n+2} $$ is divisible by $39$. Induction is done. q.e.d.

And here comes the second one. It's the same with the first actually, just one induction.

For $n=1$ and $n=2$, the proposition is true. I'm not going to write the results. We can do the induction with iterations with $3$, as we have to show it for the $n\neq3k$.

Let's start. Assume for $n$ the proposition is true, that is $5^{2n} + 5^n +1 =31t$

Check for the situation for $n+3$:

$$5^{2(n+3)}+5^{n+3} + 1 $$ $$= 5^{2n} * 15625 + 5^n * 125 + 1 $$ $$= 5^{2n} * 15625 + 125 (31t - 5^{2n}-1) + 1 \qquad Got \,5^n \,from \,the \,second\, premise$$ $$= 5^{2n} * 15625 + 31*125 - 125* 5^2n - 124 $$ $$= 5^{2n} (15625 - 125) + 31*125 - 4*31 $$ $$ = 5^{2n} * 31 * 500 + 31*125t - 4*31$$ $$ = 31(5^{2n}*500 + 125t - 4 )$$ $$ = 31*s $$

Induction is done. q.e.d.

share|improve this answer
    
Thanks very much. –  Mohsen Oct 11 '13 at 11:22
    
I've added the solution of the second one as well, in the edit. –  Zafer Sernikli Oct 11 '13 at 11:38
add comment

For one, let $\displaystyle f(n): 13^n+7^n+19^n=39k$ holds true for $n=m$ where $m$ is odd positive integer

$\implies\displaystyle13^m+7^m+19^m=39k_1$

$\implies\displaystyle13^m+7^m+19^m=13k_2\implies 7^m+19^m=13k_3\ \ \ \ (1)$

Now for $n=m+2,$

$\displaystyle13^{m+2}+7^{m+2}+19^{m+2}\equiv7^m\cdot49+19^m\cdot361\pmod{13}\equiv-3(7^m+19^m)\pmod{13}\equiv0$ [using $(1)$]

$\displaystyle13^{m+2}+7^{m+2}+19^{m+2}-(13^m+7^m+19^m)=13^m(13^2-1)+7^m(7^2-1)+19^m(19^2-1)\equiv0\pmod3$

$\displaystyle\implies 13^{m+2}+7^{m+2}+19^{m+2}\equiv13^m+7^m+19^m\pmod3\equiv0$

$\displaystyle\implies 13^{m+2}+7^{m+2}+19^{m+2}$ is divisible by lcm$(13,3)=39$ if $f(n)$ holds for $n=m$

Show that $f(n)$ holds if $n=1$


For two, let $g(n):5^{2n}+5^n+1=31t$ holds true for $n=m$

Now, $5^{2m}+5^m+1=(5^2)^m+5^m+1\equiv(-6)^m+5^m+1\pmod{31}$

$\displaystyle\implies (-6)^m+5^m+1$ is divisible by $31$

Now for $n=m+3,$

$\displaystyle (-6)^{m+3}+5^{m+3}+1-\{(-6)^m+5^m+1\}=(-6)^m\{(-6)^3-1\}+5^m(5^3-1)=(-6)^m(-217)+5^m(124)\equiv0\pmod{31}$

$\displaystyle\implies (-6)^{m+3}+5^{m+3}+1\equiv(-6)^m+5^m+1\pmod{31}\equiv0$

Now show that $g(n)$ holds for $n=1,2$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.