elementary number theory - Prove That $3^n + 8^n$ is Not Divisible by $5$ (Using Induction)

Prove that $3^n+8^n$ is not divisible by 5.

I know that this can be proved by using congruence and I am providing the proof by congruence below. But is there any way to Prove It By Induction.

The proof by congruence goes like this:

$3\equiv 3\pmod 5 \\ 3^2 \equiv 4\pmod 5 \\ 3^3\equiv 7\pmod 5 \\ 3^4\equiv 1\pmod 5 \\ 3^5\equiv 3\pmod 5$

Also,

$8\equiv 3\pmod 5 \\ 8^2 \equiv 4\pmod 5 \\ 8^3\equiv 7\pmod 5 \\ 8^4\equiv 1\pmod 5 \\ 8^5\equiv 3\pmod 5$

Adding the congruence up (since the same cycle repeats after the 4th power) none of them are divisible by 5 or equal to 0.

But I need a proof by Induction.

Any help will be appreciated.

Answer

=====Answer 3:======

It's important that one realizes that whenever they use an argument that a pattern repeats or an observation will recur indefinitely, they are fundamentally relying upon and using the Principal of induction. To wit:

They are showing something is true for a few base cases; They are (hopefully-- sometimes this step is weak---) that if it is true for some cases is will follow through for the next cases; and they make it clear that this will repeat and be true for an infinite or indefinite number of iterations.

So your argument is an argument of induction.

You've shown for base cases: $n = 1,2,3,4,5$ That $3^n + 8^n $ are none divisible by $4$.

You state that the cycle repeats. (You actually need to give a reason why the cycle repeats. That is why if $3^n + 8^n\equiv K \pmod 5$ why $3^{n+4} + 8^{n+4} $ is also $\equiv K \pmod 5$. You just noticed that $3^{5} \equiv 3^{1}$ and $8^{5} \equiv 8^{1}$ and assumed that means it is true for all $n$ and $n + 4$. You have to justify this.)

And therefore you concluded it is true for all $n$.

It is a principal if induction that allows you to conclude this.

So if you can give a reason why $3^{n+4}\equiv 3^{n}$ and $8^{n+4}\equiv 8^n$ you would be done.

(Hint: $3^{n+4} = 3^{n-1}3^5\equiv 3^{n-1}3^1 \equiv 3^n\pmod 5$. That is, after all, the reason you assumed the cycle repeated, isn't it?)

===== Answer 2: =======

You DID a proof by induction!

Notice the key phrase in you proof and the phrase that assures that you are done is:

since the same cycle repeats after the 4th power

This means that if it is true for $3^n + 8^n$ it will be true for $3^{n+4} + 8^{n+4}$ and so by induction:

As you showed a Base case that it is true for $n = 1,2,3, 4$ (as well as $n=5$ and an induction case that if it is true for $n$, we can conclude it it true for all $n = 1+4k, 2+4k, 3+4k, 4+4k$. WHich means it is true for all $n$.

That IS a prove by induction.

....

But another proof by induction follows.

===== Answer 1: ======

Well, follow the rules of a proof by induction.

Base case: $n=1$

$3^1 + 8^1 =11 $ which is not divisible by $5$.

Base case done:

Inductive case:

Assume that $3^n + 8^n$ is not divisible $5$.

Now we need to prove that thereform $3^{n+1} + 8^{n+1}$ is not divisible by $5$.

Now my advice is that when you need to prove something about $P(n+1)$ is to put it into terms of $P(n)$ and use what you know about $P(n)$.

$3^{n+1} + 8^{n+1} = 3*3^n + 8*8^n = 3*3^n + 3*8^n + 5*8^n= 3*(3^n + 8^n) + 5*8^n$ and....

$5$ is prime. $5\not \mid 3$ and $5\not \mid (3^n + 8^n)$ and $5|5*8^n$ so $5 \not \mid 3*(3^n+8^n) + 5*8^n$.

Induction step done.

Principal of induction declares we are done. Base case: $3^n + 8^n$ is not divisible by $5$ for $n = 1$. Induction case: If $3^n+8^n$ is not divisible by $5$ for a value of $n$ then in will not be divisible by $5$ for the next value of $n$. Therefore: As we can get to all values of $n$ by starting at $1$ and then going the next, and the next after that, and so on.... it must be true that $3^n +8^n$ is not divisible by $5$ for any natural $n$.

By the way...

sequences and series - Result of the product $0.9 times 0.99 times 0.999 times ...$

My question has two parts:

1. How can I nicely define the infinite sequence $0.9,\ 0.99,\ 0.999,\ \dots$? One option would be the recursive definition below; is there a nicer way to do this? Maybe put it in a form that makes the second question easier to answer.
   $$s_{i+1} = s_i + 9\cdot10^{-i-2},\ s_0 = 0.9$$
   Edit: Suggested by Kirthi Raman:
   $$(s_i)_{i\ge1} = 1 - 10^{-i}$$




2. Once I have the sequence, what would be the limit of the infinite product below? I find the question interesting since $0.999... = 1$, so the product should converge (I think), but to what? What is the "last number" before $1$ (I know there is no such thing) that would contribute to the product?
   $$\prod_{i=1}^{\infty} s_i$$

Answer

To elaborate, and extend on GEdgar's answer: there is what is called the $q$-Pochhammer symbol

$$(a;q)_n=\prod_{k=0}^{n-1} (1-aq^k)$$

and $(a;q)_\infty$ is interpreted straightforwardly. The product you are interested in is equivalent to $\left(\frac1{10};\frac1{10}\right)_\infty\approx0.8900100999989990000001$.

One can also express the $q$-Pochhammer symbol $(q;q)_\infty$ in terms of the Dedekind $\eta$ function $\eta(\tau)$ or the Jacobi $\vartheta$ function $\vartheta_2(z,q)$; in particular we have

$$\left(\frac1{10};\frac1{10}\right)_\infty=\sqrt[24]{10}\eta\left(\frac{i\log\,10}{2\pi}\right)=\frac{\sqrt[24]{10}}{\sqrt 3}\vartheta_2\left(\frac{\pi}{6},\frac1{\sqrt[6]{10}}\right)$$

---

I might as well... there is the following identity, due to Euler (the pentagonal number theorem):

$$(q;q)_\infty=\prod_{j=1}^\infty(1-q^j)=\sum_{k=-\infty}^\infty (-1)^k q^\frac{k(3k-1)}{2}$$

which, among other things, gives you a series you can use for quickly estimating your fine product:

$$\left(\frac1{10};\frac1{10}\right)_\infty=1+\sum_{k=1}^\infty (-1)^k\left(10^{-\frac{k}{2}(3k+1)}+10^{-\frac{k}{2}(3k-1)}\right)$$

Three terms of this series gives an approximation good to twenty digits; five terms of this series yields a fifty-digit approximation.

elementary number theory - Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$...

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$.

So far I have the base case completed, and believe I am close to completing the proof itself.

Base case:$(n=1)$

$3^1 + 7^1 - 2 = 8/8 = 1 $

Inductive Hypothesis: Assume that $3^n +7^n −2$ is divisible by 8 for all positive integers n.

Induction step $(n+1)$ case:

$$ 3^{n+1} + 7^{n+1} - 2 $$

$$3(3^{n}) + 7(7^{n}) - 2$$

$$3^n + 7^n = 8x $$

-It seems to me that this could be the end of the proof because whatever the answer is would be a multiple of 8: but I am unsure, any help is appreciated.

limits - Proof Verification: Show that every polynomial of odd degree with real coefficients has at least one real root.

Question: Show that every polynomial of odd degree with real coefficients has at least one real root.

Proof: $f(x)$ is of the form:

$f(x) = a_nx^n +a_{n-1}x^{n-1}+.....+a_2x^2 + a_1x +a_0$

$f(x)$ is an odd degree polynomial and is hence continuous on $\mathbb{R}$.

Then, if $f(x)$ has a positive leading coefficient

$\implies \lim_{x \to \infty}f(x)=\infty$ and $\lim_{x \to -\infty}f(x)=-\infty$

$\implies \exists \alpha,\beta \in\mathbb{R}$ with $ \alpha > \beta$ such that:

$ \alpha>0$ and $f(\alpha)>0$ and $\beta <0$ and $f(\beta)<0$

Now, consider the restriction of $f(x)$ onto the interval $I:=[\beta,\alpha]$

The restriction of $f$ on $I$ is also continuous on $I$

Then, since $f(\beta)<0

$ \exists$ a number $c \in (\beta,\alpha)$ such that $f(c) =0$

Can anyone please verify this proof and let me know if it is correct and /or if I'm missing out on something?

Note: I've missed out on the case with negative leading coefficient as I believe that too will be done in a similar fashion should this proof be alright.

Thank you.

calculus - Prove that f is integrable on [0,2]

Let

\begin{align}
f(x)=\left\{\begin{matrix}1,\:\: 0\leq x\leq 1,\\
0,\:\:1\end{matrix}\right.
\end{align}

Prove that $f$ is integrable on $\left[0,2\right]$, and find the value of
\begin{align}
\int_0^2 f\left(x\right)\:dx.
\end{align}

In order to show that $f$ is integrable I think I need to use the following theorem:

The bounded function $f$ is integrable on $\left[a,b\right]$ if and only if for
every positive number $\epsilon$ there exists a partition $P$ of $\left[a,b\right]$
such that $|U\left(f,P\right) - L\left(f,P\right)|<\epsilon$.

The problem is that I'm not sure how to actually use this theorem to show it, I dont understand how I can find the value of the integral either, any tips solution? thanks!

Answer

This function is integrable by definition because
\begin{align}
\int_0^2 f\left(x\right)\:dx=\int_0^1\:dx+\int_{1+}^2 0\:dx=1.
\end{align}

complex numbers - Why this proof $0=1$ is wrong?(breakfast joke)

We have $$e^{2\pi i n}=1$$

So we have $$e^{2\pi in+1}=e$$

which implies $$(e^{2\pi in+1})^{2\pi in+1}=e^{2\pi in+1}=e$$
Thus we have $$e^{-4\pi^{2}n^{2}+4\pi in+1}=e$$

This implies $$e^{-4\pi^{2}n^{2}}=1$$

Taking the limit when $n\rightarrow \infty$ gives $0=1$.

Answer

Your error is (as in most of those fake-proofs) in the step where you use the power law $(a^b)^c=a^{bc}$ without the conditions of that power law being fulfilled.

sequences and series - Sum equals integral

It is quite a well known fact that:
$$\int_0^{+\infty} \frac{\sin x}{x} \, dx = \frac{\pi}{2}$$
also the value of related series is very similiar:
$$\sum_{n = 1}^{+\infty} \frac{\sin n}{n} = \frac{\pi - 1}{2}$$

Combining these two identities and using ${\rm sinc}$ function we get:
$$\int_{-\infty}^{+\infty} {\rm sinc}\, x \, dx = \sum_{n = -\infty}^{+\infty} {\rm sinc}\, n = \pi$$
What is more interesting is the fact that the equality:
$$\int_{-\infty}^{+\infty} {\rm sinc}^k\, x \, dx = \sum_{n = -\infty}^{+\infty} {\rm sinc}^k\, n$$
holds for $k = 1,2,\ldots, 6$. There are some other nice identities with ${\rm sinc}$ where sum equals integral but moving on to other functions we have e.g.:
$$\sum_{n = -\infty}^{+\infty} \binom{\alpha}{n} e^{int} = \int_{-\infty}^{+\infty} \binom{\alpha}{n} e^{itx} \, dx = (1+e^{it})^\alpha, \; \alpha >-1$$which is due to Pollard & Shisha.

And finally the identity which is related to the famous Sophomore's Dream:
$$\int_0^1 \frac{dx}{x^x} = \sum_{n = 1}^{+\infty} \frac{1}{n^n}$$
Unfortunately in this case the summation range is not even close to the interval of integration.

Do you know any other interesting identities which show that "sum = integral"?

Answer

Several papers are dedicated to the subject of integrals of functions that equal the sum of the same function, primarily for estimation purposes.

Boas and Pollard (1973) has some interesting sum-integral equalities:

$$\pi/\alpha=\sum_{n=-\infty}^\infty \frac{\sin^2 (c+n)\alpha}{(c+n)^2}=\int_{-\infty}^\infty \frac{\sin^2 (c+n)\alpha}{(c+n)^2}\, \text{d}n$$

$$\pi\operatorname{sgn} a=\sum_{n=-\infty}^\infty \frac{\sin (n+c)\alpha}{n+c}=\int_{-\infty}^\infty \frac{\sin (n+c)\alpha}{n+c}\, \text{d}n$$

It also gives several general formulae for functions that suffice:

$$\sum_{n=-\infty}^\infty f(n)=\int_{-\infty}^\infty f(n) \, \text{d}n$$

mainly with Fourier analysis.

---

This paper gives an equality with the Bessel J function:

$$\int_{-\infty}^\infty \frac{J_y (at) J_y(bt)}{t}\, \text{d}t=\sum_{t=-\infty}^\infty \frac{J_y (at) J_y(bt)}{t}$$

and some more references:

There have been a number of studies of this kind of sum-integral
equality by various groups, for example, Krishnan & Bhatia in the
1940s (Bhatia & Krishnan 1948; Krishnan 1948a,b; Simon 2002) and Boas,
Pollard & Shisha in the 1970s (Boas & Stutz 1971; Pollard & Shisha

1972; Boas & Pollard 1973).

---

See also Surprising Sinc Sums and Integrals which has some other equalities. This paper also states that (paraphrasing)

If $G$ is of bounded variation on $[−\delta, \delta]$, vanishes outside $(−α, α)$, is Lebesgue integrable over $(−α, α)$ with $0 < α < 2\pi$ and has a Fourier transform of $g$, then

$$\sum_{n=\infty}^\infty g(n)=\int_{-\infty}^\infty g(x)\, \text{d}x+\sqrt{\frac{\pi}{2}}(G(0-)+G(0+))$$

---

Ramanujan's second lost notebook contains some sums of functions that equal the integral of their functions (Chapter 14, entries 5(i), 5(ii), 16(i), 16(ii)).

---

If you want, even more references with examples are in the papers I have mentioned.