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
1answer
45 views

understanding a proof which uses induction on the length of a formula

This comes from Shoenfield's textbook Mathematical Logic. Here is the theorem and its proof: If $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators and $u_1\dots u_n$ and $u_1'\dots u_n'$ are ...
3
votes
0answers
26 views

Can you please comment on and check these couple of induction proofs?

So the following statements need to be proved: 1) $(1+a_1)(1+a_2)\cdots(1+a_n)>1+a_1+a_2+\cdots+a_n$ for $a_i>0,(i=1,2,\ldots,n)$ and $n\ge2$ 2) $(1-a_1)(1-a_2)\cdots(1-a_n)<1-(a_1+a_2+\...
3
votes
1answer
63 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 ...
0
votes
1answer
20 views

Prove if $x_1,…,x_n$ are natural numbers with $n\geq2$ then $x_1x_2…x_n$ is odd iff $x_i$ is odd for all $i$, $1\leq i\leq n$

I am not sure if Im on the right track here but if any one could help out I would greatly appreciate it. Prove if $x_1,...,x_n$ are natural numbers with $n\geq2$ then $x_1x_2...x_n$ is odd iff $...
1
vote
6answers
88 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 ...
2
votes
4answers
6k views

Proof by induction that $ \sum_{i=1}^n 3i-2 = \frac{n(3n-1)}{2} $

I'm starting to understand how induction works (with the whole $k \to k+1$ thing), but I'm not exactly sure how summations play a role. I'm a bit confused by this question specifically: $$ \sum_{i=1}^...
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}...
0
votes
0answers
31 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
78 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
33 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
44 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
7answers
3k views

Prove $n^2 > (n+1)$ for all integers $n \geq 2$

I understand that I need to use induction for this, that's not a problem. I get stuck after I try to invoke the inductive hypothesis. $P_n: n^2 > n+1$... and we want to prove $P_{n+1}: (n+1)^2 >...
1
vote
4answers
63 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$?
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}...
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 \...
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 ...
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$ ...
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 ...
1
vote
6answers
163 views

Proving that $64$ divides $3^{2n+2}+56n+55$ by induction

Let $n ≥ 0$ be an integer. Prove by induction: 64 divides $3^{2n+2} + 56n + 55$ general expression: $3^{2n+2} + 56n + 55 = 64m$ 1st I substitute $P(0)$ and it gives me true: $9+55 = 64$ (if m = 1 ...
-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?
4
votes
2answers
70 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
1answer
1k views

Concrete Mathematics - The Josephus Problem

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + 1$...
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 ...
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 ...
47
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
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 ...
32
votes
9answers
9k views

Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction

How can I prove that $$1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$ for all $n \in \mathbb{N}$? I am looking for a proof using mathematical induction. Thanks
1
vote
2answers
41 views

Discrete Math Induction Proof Help With Question

I currently have to do this following proof using induction (base case, inductive hypothesis required) $$\sum_{i=1}^n(6i-3)=3n^2, \forall n>1$$ I'm not really sure how to approach this question ...
2
votes
1answer
67 views

Knuth algorithm on constructing a proof

I'm going through mathematical induction section of Knuth's book "The Art of Computer Programming" (pg. 11). I'm having a hard time understanding Algorithm I on constructing a proof. Here is the ...
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$$
1
vote
1answer
53 views

'Mathematical Induction'

Use mathematical induction to prove that $4^n -3^n + 1 = 7a_{n-1} – 12a_{n-2} + 6$ with $n \ge 3$ with the initial condition $a_1 = 2$ and $a_2 = 8$ . Given that $a_n = 4^n -3^n + 1$. I am confused ...
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 ...
5
votes
5answers
15k views

Induction proof on Fibonacci sequence: $F(n-1) \cdot F(n+1) - F(n)^2 = (-1)^n$

I can't seem to solve this problem. It is: The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows: \begin{align} F(0) &::= 0 \\ F(1) &::= 1 \\ F(n) &::= F(n-1) + F(...
0
votes
0answers
2k views

If $s_{k,m}(n) =\sum_{i=n+1}^{kn+m} \frac1{i} $ show that for $k \ge 2m+1$, $s_{k,m}(n+1)>s_{k,m}(n)$ and $s_{k,m}(n+1)-s_{k,m}(n) <\frac1{n(n+1)} $

Let $s_{k,m}(n) =\sum\limits_{i=n+1}^{kn+m} \frac1{i} $. Show that, for $k \ge 2m+1$, $s_{k,m}(n+1)>s_{k,m}(n)$ and $s_{k,m}(n+1)-s_{k,m}(n) <\frac1{n(n+1)} $ so that $s_{k,m}(n) < s_{k,m}(...
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
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 ...
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 ...
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 ...