# Tagged Questions

For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

70 views

### Prove $n^2 \geq n$ for every integer

I am having some trouble with this proof. Part of it is that I have to prove it for every integer. Does this mean I have an inductive step that goes for $P(k+1)$ and $P(k-1)$? Assuming my base case ...
66 views

### Prove using induction on n that: $8\mid5^n+2(3^{n-1})+1$

How can we use induction to prove that $8\mid5^n+2(3^{n-1})+1$ for any natural $n$?
24 views

### Proving an upper bound on the terms of a sequence defined defined by a recurrence relation

Problem: Suppose $R>0$, $x_0 >0$ and $$x_{n+1}=\frac{1}{2}\left(\frac{R}{x_n}+x_n\right)$$ $n \geq 0$. Prove,$$x_n - \sqrt{R} \leq \frac{(x_0-\sqrt{R})^2}{2^nx_0}$$ for $n \geq 1$. My ...
115 views

### Prove that if $n|5^n + 8^n$, then $13|n$ using induction

I have to prove using mathematical induction that if $n \ge 2$ and $n|5^n + 8^n$, then $13|n$. Please help me.
105 views

### Proof that $3^n | 2^{3^n} + 1$

Question: Proof by induction that $3^n | 2^{3^n} + 1$. Attempt: $$2^{3^{n+1}} + 1 = 2^{3^n} 2^3 + 1 = 2^{3^n} 2^3 + 1 + 2^3 - 2^3 = 2^3( 2^{3^n} + 1 ) + 1 -2^3$$ And the first is $3^n |$ ...
45 views

### How to generalize the principle of mathematical induction for proving statements about more than one natural number?

Suppose that $P(n_1, n_2, \ldots, n_N)$ be a proposition function involving $N >1$ positive integral variables $n_1, n_2, \ldots, n_N$. Then how to generalise the familiar induction to prove this ...
76 views

45 views

63 views

51 views

### Use mathematical induction to prove that $n^ 3 − n$ is divisible by 3 whenever n is a positive integer.

Solution: Let $P(n)$ be the proposition “$n^3−n$ is divisible by $3$ whenever $n$ is a positive integer”. Basis Step:The statement $P(1)$ is true because $1^3−1=0$ is divisible by $3$. This completes ...
90 views

### Proving by induction that $n! < (\frac{n+1}{2})^n$.

As an analysis homework I have to prove by induction that $n! < (\frac{n+1}{2})^n : (2 \le n \in\mathbb{N})$ For $n = 2$ this is trivial, but for $n+1$ no matter how I transform the equation I ...
19 views

### In a directed graph with n≥2 nodes, if two different nodes reaches every nodes (including itself), then this graph is strongly connected.

I think this statement is true because if node a can reach every node (including node b) and node b can reach every node (including node a), there is an edge between node a and node b. This means that ...
44 views

### Induction with Turing machines.

how would I go about proving by induction that the Turing Machine pictured below, that if it is started with a blank tape, after 10n+6 steps the machine will be in state [3] with the tape reading . . ...
66 views

24 views

### Mathematical Induction to show positive real number other than 1

By mathematical induction I need to show that $a$ is a positive real number other than $1$, then $$\sum^n_{j=1}{a^j}=(a)\frac{1-a^n}{1-a}$$ For each natural number $n$. We us ethe first principle ...
### Prove that $\displaystyle \sum_{k=1}^n \bigg(\dfrac{1}{k}+\dfrac{2}{k+n}\bigg ) \leq \ln(2n) + 2 -\ln(2)$
Prove that $$\displaystyle \sum_{k=1}^n \bigg(\dfrac{1}{k}+\dfrac{2}{k+n}\bigg ) \leq \ln(2n) + 2 -\ln(2).$$ I was thinking of using mathematical induction for this. That is, We prove by induction ...