# 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 ...

26 views

### Set-Theoretic Probability

Consider $\{B_i | i \in I\}$ be a collection of events where $I$ is an arbitrary index set. I would like to show that $$\left(\bigcup_{i \in I} B_i\right)^c = \bigcap_{i \in I} B_i^c.$$ My friend ...
61 views

50 views

### Prove $\forall n \geq 10, 2^n > n^3$

Prove $\forall n \geq 10, 2^n > n^3$ base case: $n = 10$ $2^{10} = 1024$ $10^3 = 1000$ $1024 > 1024$. So $P(k)$ holds for $k = n$. We seek to show $P(k+1)$ holds: We know $2^k > k^3$. ...
43 views

### Overspill in computable nonstandard models

Tennenbaums' theorem does not apply to Robinson Arithmetic ($Q$). There is a computable, nonstandard model of $Q$ "consisting of integer-coefficient polynomials with positive leading coefficient, plus ...
44 views

### Show that an inequality is true using mathematical induction and the mean value theorem

A question in my math book is: "Use mathematical induction to show that: $$e^x>1+x+\frac{x^2}{2!}+...+\frac{x^n}{n!}$$ if $x>0$ and $n$ is any positive integer." Apparently the solution ...
110 views

### Formula for sum of first $n$ odd integers

I'm self-studying Spivak's Calculus and I'm currently going through the pages and problems on induction. This is my first encounter with induction and I would like for someone more experienced than me ...
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 ...
68 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

64 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 ...
45 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 . . ...
### How to prove that $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$.
So I've been struggling with this sum for some time and I just can't figure it out. I tried proving by induction that if the sum above is a $S_n$ then $S_{n+1} = 4S_n$, but I didn't really succeed so ...