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

0
votes
4answers
56 views

Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
0
votes
0answers
29 views

How to get a feel for rigor/form used in mathematics?

I'm an engineer, and while you get introduced to many concepts of mathematics, but only with a subset of the vocabulary, and none of the rigor and proofs. So while trying to read a mathematical book, ...
4
votes
5answers
75 views

Inequality : $\displaystyle \sum_{k=1}^n x_k\cdot \displaystyle \sum_{k=1}^n \dfrac{1}{x_k} \geq n^2$

I have to show the inequality of $$\left(\sum_{i=1}^n x_i\right)*\left(\sum_{i=1}^n \frac{1}{x_i}\right) \geq n^2.$$For $x_1, ... x_n \in \mathbb{R_{>0}}$ and $ n \geq 1$. I wanted to show this ...
2
votes
1answer
32 views

Well-ordering principle and theorem

Could somebody clearly explain the difference between the well-ordering principle and the well-ordering theorem? Is one of these related to the Principle of Mathematical Induction, and the other to ...
0
votes
1answer
40 views

Fibonacci Sequence: Prove $f_1+f_3+\dots+f_{2n-1}=f_{2n}$ by Induction.

I believe the majority of my proof is correct I'm just not certain about the base case if any one can explain how to do that base case or fix any error I made I would greatly appreciate it. Recall ...
3
votes
2answers
26 views

induction proof over graphs

I have a question about how to apply induction proofs over a graph. Let's see for example if I have the following theorem: Proof by induction that if T has n vertices then it has n-1 edges. So what ...
-1
votes
0answers
14 views

trouble undestanding the proof for the therom “If x is element of N and x != 1, then there is a unique y so that x = y'.”

give the following axioms The following theorem is proven Im having trouble understanding the sentence from "if x=1 then x' element of N ..." up to "and by definition of A, x' element of A." ...
0
votes
1answer
54 views

proof of an equivalence

I am trying to prove something by induction, and in induction step I had to prove this $$1+ \sum_{k=1}^{\lceil{\frac{n-1}{2}}\rceil} (-1)^{k}\frac{(t^2)^{2k}}{(2k)!} = \sum_{k=0}^{\lfloor{\frac{n}{2}}\...
2
votes
3answers
48 views

induction clarification about the step $n+1$

Suppose i need to prove that $\frac{1}{2^2}+\frac{1}{3^2}...+\frac{1}{n^2}<1-\frac{1}{n}$ So in the step of $n+1$, the right side becomes $<1-\frac{1}{n+1}$ or is it: $<1-\frac{1}{n}-\frac{1}...
2
votes
1answer
70 views

Strange Algebra

I am working on a mathematical induction worksheet and my professor gave us the key and I have run across something that makes zero sense to me so please explain if you can. Additional info: $k \ge2$ ...
3
votes
2answers
54 views

Prove that $\Gamma(-k+\frac{1}{2})=\frac{(-1)^k 2^k}{1\cdot 3\cdot 5\cdots(2k-1)}\sqrt{\pi}$.

I was able to prove that $$ \Gamma\left (k+\frac{1}{2} \right )=\frac{1\cdot 3\cdot 5\cdots(2k-1)}{2^k}\sqrt{\pi}.\tag{$k\geq 1$}$$ using the Legendre's duplication formula. But I can't do the same to ...
1
vote
3answers
61 views

Finding a closed form for $\sum^{n}_{k=1} \frac{k}{(k+1)!} $

I'm finding a closed form to $\sum^{n}_{k=1} \frac{k}{(k+1)!} (n \leq 1) $ (in a environment of induction and recurrence) I've been trying to solve it without success, can anybody help me (?) The ...
-4
votes
0answers
15 views

there exists a gray code of length 2k for any positive integer k [closed]

Can any one help me prove the statement "there exists a gray code of length 2k for any positive integer k" using mathematical induction thanks
0
votes
2answers
59 views

Mathematical induction: $4 + 5 + 6 + … + n = \dfrac{n(n+1)}{3}$ where $(n \ge 4)$

Prove using mathematical induction that 4 + 5 + 6 + … + n = [n(n+1)] / 3 (n is an integer >= 4) I just wanted to confirm because my Base case P(4) is false. So this statement can't be proven?
-1
votes
1answer
35 views
0
votes
1answer
39 views

Prove by mathematical induction cos/sin question [closed]

Knowing that $$\sin 2nx = \sin((2n+1)x) \cos x - \cos((2n + 1)x) \sin x$$ Prove by induction that: $$\cos x + \cos 3x + \cos 5x + \cdots + \cos((2n - 1)x) = \dfrac{\sin 2nx}{2\sin x}$$ For all $n$...
3
votes
1answer
35 views

Need help with Knuth's proof for Gray Codes

I am reading Knuth's "The Art of Computer Programming" Volume 4 Fascicle 2A. Needless to say I am pretty poor in Mathematics and I need help understanding some of the proofs. If anyone has any ...
4
votes
2answers
69 views

Proving that $f_2+f_4+\cdots+f_{2n}=f_{2n+1}-1$ for Fibonacci numbers by induction

Given: $f_1 = f_2 = 1$ and for $n \in\mathbb{N}$, $f_{n+2} =f_{n+1} + f_n$. Prove that $f_2 + f_4 + \dots + f_{2n} = f_{2n+1}- 1$. Would you start with setting $f_2 + f_4 + \dots + f_{2n}= ...
3
votes
3answers
36 views

Using 4-cent and 11-cent stamps for postage (induction)

I was wondering how many base cases are needed and when to stop (in general). For example, I have 4-cent and 11-cent stamps and I need to determine the amount of postage I can make, the cases I have ...
1
vote
3answers
60 views

Proving that $3 + 3 \times 5 + 3 \times 5^2 + \cdots+ 3 \times 5^n = [3(5^{n+1} - 1)] / 4$ whenever $n \geq 0$

Use induction to show that $$3 + 3 \times 5 + 3 \times 5^2 + \cdots+ 3 \times 5^n= \frac{3(5^{n+1} - 1)}{4} $$whenever $n$ is a non-negative integer. I know I need a base-case where $n = 0$: $$3 \...
0
votes
2answers
20 views

Strong Induction issue

I am trying to prove a statement using strong induction but I seem to be getting stuck. I don't know if did something wrong or I am just not recognizing an opportunity for factoring/how to factor ...
-4
votes
4answers
54 views

prove by mathematical induction $1^{3}+2^{3}+…+n^{3}=(n(n+1)/2)^{2}$ [duplicate]

I already done the basis step or prove of one p(1). From this point,this is my hypothesis: $k^{3}$=$(k(k+1+1)/2)^{2}$ I wish to prove that my hypothesis is equal to $(k+1)^{3}$=$(k+1(k+1+1)/2)^{2}$ ...
-2
votes
0answers
30 views

Show the sum of the squares of the first $n$ positive integers is $[n(n+1)(2n+1)]/6$ for all $n$ greater than or equal to $2$ [duplicate]

I need to show by proof that the statement: The sum of the squares of the first n positive integers is $[n(n+1)(2n+1)]/6$ for all n greater than or equal to $2$ is true. I know im going to ...
-3
votes
1answer
44 views

A couple of identities to prove by induction [closed]

$\left(\frac{a+b}2\right)^n \le \frac{a^n+b^n}2$ for $a>0$, $b>0$ and $n\ge2$ $(1+a_1)(1+a_2)\dots(1+a_n) > 1+a_1+a_2+\dots+a_n$ for $a_i>0$ and $n\ge2$ $(1-a_1)(1-a_2)\dots(1-a_n) <...
3
votes
2answers
88 views

Prove that $(n!)^2 ≥ n^n$ using mathematical induction [duplicate]

1° $n_0=1$ $(1!)^2 \ge 1^1$ $1\ge1$ 2° $k \ge n_0$ assumption: $$(k!)^2 \ge k^k$$ and for k+1: $$((k+1)!)^2 \ge (k+1)^{k+1}$$ I also noticed that: $$((k+1)!)^2 = (k!)^2 * (k+1)^2$$
5
votes
2answers
65 views

Proving by induction that the sequence $a_{n+1}=\sqrt{3a_n-1}$ is increasing

$a_1=1$; $a_{n+1}=\sqrt{3a_n-1}$ $\quad$ $(n\ge1)$ Now I have to show it is true for $n=1$, which is easy. I have to assume it is true for $n=k$, therefore: $\sqrt{3a_{k}-1}$ $\gt$ $\sqrt{3a_{k-...
0
votes
3answers
54 views

Why do you need to show A(1) before proving A(n) by induction? [duplicate]

My instructor stated that in order to have a valid proof by mathematical induction, you first have to show A(1) holds, and then assume A(n) to deduce A(n+2). Why is the first step necessary if we are ...
3
votes
4answers
137 views

Prove if $n \in \mathbb N$, then $\frac{1}{2!}+\cdots+\frac{n}{(n+1)!}=1-\frac{1}{(n+1)!}$

Prove if $n \in \mathbb N$, then $\frac{1}{2!}+\frac{2}{3!}+\frac{3}{4!}+\cdots+\frac{n}{\left(n+1\right)!} = 1-\frac{1}{\left(n+1\right)!}$ So I proved the base case where $n=1$ and got $\frac{1}{2}...
3
votes
1answer
38 views

Double induction - another method?

I am going through some good old Fibonacci proof by induction problems that require two counters $m, n$ instead of one. In order to prove $P(m, n)$ for all $m,n \in \mathbb{N}$, I am thinking of ...
0
votes
1answer
46 views

What am I missing in this induction proof?

Prove that if $g:\mathbb{N}\rightarrow \mathbb{N}$ and $\forall x,y\in \mathbb{N}, x<y\Rightarrow g(x)<g(y)$ then $n\leq g(n)\space\space\space \forall n\in \mathbb{N}$ My proof so far (...
1
vote
0answers
28 views

Empty Twin Prime Sets

Consider this set of numbers: $1, 5, 8, 11, 13, 31, 37, 53, 61, 73, 79, 97, 122, 127$ This is the set of numbers $n$ such that $nm \pm 1$ is not a twin prime pair for all $m \leq n$. For instance, $...
1
vote
3answers
68 views

Proof by math induction with inequality example, why is “replacement” allowed?

I have trouble with the understanding of mathematical induction concerning inequalities. For example, the question is: Prove by mathematical induction that $ n ^ 2 <2 ^ n $ if $ \forall n \in {N}$ ...
0
votes
0answers
15 views

Prove that reverse of regular L is also regular [duplicate]

Prove that reverse of regular language is also regular. I know, how i can to this by using DFA of L. Changing directions of edges and so on. But how can it be done with Structural induction? What ...
0
votes
2answers
49 views

Is this type of proof by induction correct in Sylow's Theorem?

The following is the first part of the Sylow's Thm: My question is: if order of $G$ was $p^a$ (and not $p^am$) then we could start with $|G|=1$ which means $a=0$. Then supposed that the theorem ...
1
vote
6answers
83 views

Prove by induction the particular inequality $\left(1.3\right)^n \ge 1 + \left(0.3\right)n$ for every $n \in \mathbb N$

$\left(1.3\right)^n \ge 1 + \left(0.3\right)n$ for every $n \in \mathbb N$ Not sure where I'm going wrong in my Algebra, but I assume it's because I'm adding an extra term. Is the extra term ...
0
votes
1answer
43 views

Strong Induction for Fibonacci number related identity $f_{n-m} = f_{m}f_{n+1} + f_{m-1} f_n$ [closed]

Let $f_n$ be the $n^{th}$ Fibonacci number. Let $m$ be a fixed strictly positive integer. Prove by strong induction that for all $n\ge 0$, $$f_{n+m} = f_{m}f_{n+1} + f_{m-1} f_n$$ edit: $f_{n+m} = ...
1
vote
2answers
24 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
56 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
36 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
35 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
49 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
41 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
43 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
109 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
68 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
61 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
22 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
114 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.