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

learn more… | top users | synonyms

1
vote
2answers
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 ...
2
votes
0answers
61 views

Determinant of a block matrix $2n$ by $2n$

Consider the block $2n \times 2n$ matrix $$\begin{bmatrix} A&B\\ 0&D \end{bmatrix}$$ where $A,B,D$ are $n \times n$ blocks. Show that $$\det\begin{bmatrix} A&B\\ 0&D \...
1
vote
1answer
37 views

Induction problem for $U_{n+1}(x) = 2x U_n(x) - U_{n-1}(x),$ what can be assumed?

I have this straightforward induction problem that perhaps I am over thinking at this time of the morning. Here it is: $U_1(x) = 1, \; U_2(x) = 2x, \; U_{n+1}(x) = 2x U_n(x) - U_{n-1}(x).$ Prove ...
3
votes
0answers
39 views

Proof by “continuous induction”

There’s a method of proving inequalities over some interval of real numbers using differentiation. For instance to prove that $x-\log(1+x) \geqslant 0$ whenever $x \geqslant 0$ we can differentiate ...
1
vote
2answers
41 views

Proving by induction that $\sum\limits_{i=1}^n\frac{1}{n+i}=\sum\limits_{i=1}^n\left(\frac1{2i-1}-\frac1{2i}\right)$

I have a homework problem to prove the following via induction: $$\sum_{i=1}^n \frac{1}{n+i} = \sum_{i=1}^n \left(\frac{1}{2i-1} - \frac{1}{2i}\right) $$ The base case is true. So far I've done the ...
3
votes
1answer
41 views

Need hint on induction proof for summation

I have a homework problem to prove the following via induction: $$\sum_{i=1}^n i^22^{n-i} = 2^{n+3}-2^{n+1}-n^2-4n -6$$ The base case is true. I generated the below using $s_k+a_{k+1}=s_{k+1}$: $$ 2^{...
2
votes
2answers
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$. ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
5
votes
8answers
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 ...
0
votes
3answers
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 ...
1
vote
4answers
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$?
1
vote
1answer
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 ...
1
vote
2answers
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.
1
vote
4answers
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 |$ ...
1
vote
2answers
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 ...
0
votes
3answers
76 views

Proof that combinations are equal to coefficients in the binomial expansion

Let $n\in N$, $k\in Z$, $o\leq k \leq n$. Define $C^{n}_k$ as the coefficient of $x^{n-k}y^k$ in the expansion of $(x+y)^n$ $$(x+y)^n= \sum^{n}_{k=0} C^{n}_k x^{n-k}y^k$$ Prove that ${C^{n}_{k}}={...
0
votes
5answers
432 views

Mathematical induction using Sigma [closed]

I have attached an image of a kind of mathematical induction question that i have never seen before. I attached it because i don't know how to type all the symbols out properly, i'm sorry again would ...
0
votes
3answers
50 views

Proof by induction (binomial theorem)

Let $n\in N$, $k\in Z$, $o\leq k \leq n$. Define $C^{n}_k$ as the coefficient of $x^{n-k}y^k$ in the expansion of $(x+y)^n$ $$(x+y)^n= \sum^{n}_{k=0} C^{n}_k x^{n-k}y^k$$ Use induction to prove ...
0
votes
1answer
59 views

Is there a key difference between the principle of transfinite induction and the principle of transfinite induction for ordinals?

In a recent question I was asked to prove the principle of transfinite induction for ordinals but I mistakenly proved the principle of transfinite induction, since I have a only a vague understanding ...
1
vote
0answers
46 views

Is there such a thing as “finite” induction?

I am not sure of the terminology that I am looking for, but I would like to use an inductive proof on the following type of structure. I have something of the form, for every $n \geq 2$ and for any $1 ...
0
votes
2answers
45 views

Prove the sequence of partial sums is monotonically increasing

Consider the series: $$\sum_{k=0}^{\infty}\frac{1}{k!}$$ Prove that the sequence of partial sums ($s_{n}=\sum_{k=0}^{n}\frac{1} {k!}$) $n>0$ is monotonically increasing. My approach: $$s_{1}= 1,\...
4
votes
2answers
340 views

Dividing a Checkerboard into L-Shaped Regions

In preparation for the GRE Math-Subject test, and honestly for the fun of it, I've been working through a select number of my texts. The first of which is Saracino's Abstract Algebra text. I was ...
0
votes
0answers
36 views

One of the faulty Induction Proof examples

P(n1): For every location of Bill in a 2n × 2n courtyard, there exists a tiling of the remainder. P(n2): I can lift all the sand on the beach. We disprove P(n2) saying that it is a bogus assumption ...
3
votes
6answers
55 views

Using induction to prove for $n ≥ 1, $ $1 \times 5+2\times6+3\times7 +\cdots +n(n + 4) = \frac 16n(n+1)(2n+13).$

This is a very interesting problem that I came across in an old textbook of mine. So I know its got something to do with mathematical induction, which yields the shortest, simplest proofs, but other ...
48
votes
16answers
4k views

How can you prove that $1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$ without using induction?

Using mathematical induction, I have proved that $$1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$$ for every integer $n > 0$. I would like to know if there is another way of proving this result ...
0
votes
1answer
33 views

Prove that $\text{det}(A)=p_1p_2-ba={bf(a)-af(b)\over b-a}$

Let $f(x)=(p_1-x)\cdots (p_n-x)$ $p_1,...p_n\in \mathbb R$ and let $a,b\in \mathbb R$ such that $a\neq b$ Prove that $\text{det} A={bf(a)-af(b)\over b-a}$ where $A$ is the matrix: $$\begin{pmatrix}...
0
votes
3answers
64 views

Mathematical Induction proof $\sum_{k=0}^n 11^k$

I have a question about methematical induction. I have to proof that: $\require{cancel}$ $$\sum_{k=0}^n 11^k$$ Knowing that: $$\sum_{k=0}^n a^k = \frac{1 - a^{k+1}}{1-a} $$ I have the base: $$ 11^...
2
votes
3answers
50 views

Recursion Proof by Induction

Given: f(1) = 2 f(n) = f(n-1) + 3, for all n>1 It can be evaluated to: ...
3
votes
1answer
46 views

Count integer squares coordinates

Let $n$ be given an natural number. We want to find the number of squares which have corners with integer coordinates between $0$ and $n$. For example $n=1$, there is only one square; $n=2$ there are ...
0
votes
2answers
41 views

Proof series decreases by induction

I have a question regarding a proof by induction. We have to see whether or not the following series converges. $$U_n = \frac{1 \cdot 4 \cdot 7 \cdots (3n - 2)}{2 \cdot 5 \cdot 8 \cdots (3n-1)}$$ I ...
1
vote
2answers
30 views

Prove identity by induction

Recently I read in lecture notes that for $\alpha \in \mathbb{N}^m$ with $\vert\alpha\vert = r$ the following identity holds: $$ \sum_{} \frac{1}{\alpha!} = \frac{m^r}{r!}.$$ Appearently one can ...
1
vote
3answers
53 views

The proof of the base case in proof by induction must always be to verify the claim is true for the number 1.

The question asks me to state True or False. Answer: I prefer True. I'm I correct?
0
votes
1answer
19 views

Induction proof for a stochastic process.

Let $(X_n)_{n\in\mathbb{N}}$ be a Markovchain. How can I then show following equation for all $ n \in \mathbb{N}$, $ \displaystyle\bigcup_{k=1}^n \lbrace X_k = j \rbrace = \biguplus_{k=1}^n \lbrace ...
0
votes
3answers
61 views

exponential function and mathematical induction

May I ask how to solve the problem? Use mathematical induction to prove that for $x\geq0$ and positive integer $n$, $$e^x \geq 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^n}{n!}$$
1
vote
3answers
38 views

Arithmetic sequence whose any five consecutive elements contain a prime

Consider an arithmetic sequence $\{11 + 13k : k\in\mathbb{N}\cup\{0\} \}$ Does this sequence contain five consecutive composites? If we look at some selections of five consec. elements: $$11, 24, 37, ...
0
votes
4answers
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 ...
4
votes
5answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 . . ...
1
vote
2answers
66 views

Induction Proof of Taylor Series Formula

I'm attempting to prove a formula for the taylor series of function from a differential equation. The equation is $$f(0)=1$$ $$f'(x) = 2xf(x)$$ I have found empirically that $$f(x) = \sum_{k=0}^{\...
1
vote
3answers
29 views

Let $G$ be a graph with $n$ vertices where every vertex has a degree of at least $\frac{n}{2}$. Prove that G is connected.

First question, if the problem uses a fraction such as $\frac{n}{2}$, would we round down in case $n$ is odd? As for the actual problem, I'm trying to do this with induction and contrapositive and ...
1
vote
2answers
40 views

Showing that $\sum_{j=0}^n (j+1) =\frac{(n+1) (n+2)}{2}$ whenever $n$ is a nonnegative integer.

First of all this is a mathematical induction proof. I faced difficulties just with the step 1 when verifying that $P(1)$ is true. Where $n=1$, the L.H.S is $$\sum_{j=0}^n (j+1)=0+1=1$$ Here I faced ...
3
votes
1answer
55 views

Find the mistake of the following inductive proof: all algorithms have the same time complexity

I came across this problem: Find the mistake of the following inductive proof: Theorem: all algorithms have the same time complexity. Proof: (By induction on the number of algorithms.) The ...
3
votes
3answers
55 views

How to demonstrate that $2^{2^n - 2} + 1$ is a nonprime number?

This, considering $n ≥ 3$. I have tried by induction; I suppose that it's true for all n less than or equal to k (and greater than or equal to 3), but then I stride when I go to prove for n = k + 1. ...
1
vote
1answer
43 views

The analytic extension of $\sum_{k=1}^n\frac1k$ and an induction

The analytic extension of the sum of the first $n$ reciprocals is given as $$\sum_{k=1}^n\frac1k=\int_0^1\frac{x^n-1}{x-1}dx$$ I am wondering if $\frac1{n+1}+\sum_{k=1}^n\frac1k=\sum_{k=1}^{n+1}\...
0
votes
2answers
39 views

Mathematical Induction with series and factorials.

I wish to show the following $$ a_{n}=\sum_{k=0}^{n}\frac{1}{(2k+1)!(2(n-k)+1)!}=\sum_{k=0}^{n+1}\frac{1}{(2k)!(2(n+1-k))!}=b_{n+1} $$ for $n\geq0$ and wish to do it using induction. I've shown it ...
0
votes
7answers
72 views

I'm having trouble understanding why inductive proofs are logical [duplicate]

I am new to Mathematics, reading books in my free time. I have recently learned about proving Mathematical propositions by induction. I am having a bit of trouble understanding the process and why it ...
1
vote
2answers
78 views

Prove with induction that $\sum_{k=0}^{n-1}x^{k}=\frac{x^n-1}{x-1}$

Suppose that $x\ne 1$ and $n\in\mathbb{N}^*$. Prove with induction that $$\sum_{k=0}^{n-1}x^{k}=\frac{x^n-1}{x-1}$$ It seems simple but I have tried for I don't know how long by now... Anyone can ...
12
votes
6answers
213 views

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