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
2answers
24 views

Full binary tree theorem proof validity?

I'm reviewing some of the theorems that make up the Full binary tree theorem and want to make sure my proof for how the number of internal nodes $I$ is related to the number of total nodes $N$ is ...
11
votes
4answers
5k views

Questions on “All Horse are the Same Color” Proof by Complete Induction

The following has been bugging me, and I can't go to sleep until I resolve it. Here is a summary of the document on page 109 of http://courses.csail.mit.edu/6.042/spring12/mcs.pdf. False ...
2
votes
2answers
27 views

Induction Sum of all odd Numbers

Show that $\sum_{k=1}^{n}(2k-1)=n^2$ Beginning: n=1 $\sum_{k=1}^{1}(2k-1)=(2*1-1)=1=1^2$ Let $\sum_{k=1}^{n}(2k-1)=n^2$ be true, then for n=p+1 $\sum_{k=1}^{p+1}(2k-1)=(p+1)^2$ has to be true too....
2
votes
2answers
52 views

Proving that $\frac{1}{4(5)}+\frac{1}{5(6)}+\frac{1}{6(7)}+\cdots+\frac{1}{(n+3)(n+4)}=\frac{n}{4(n+4)}$ by induction

I've proved the base case where $n=1$ and made the assumption that $n=k$ is true, but I'm stuck on the $n=k+1$ part. I just cannot seem to get the algebra to work in my favor. Here is the original:...
3
votes
2answers
30 views

Pattern with the the titration of summations.

While dealing with a question with finding an explicit form for a sequence I noticed something: $$\sum_{x_0=0}^{n-1} 1=\frac{n}{1!}$$ $$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1=\frac{n(n-1)}{2!}$$ ...
3
votes
5answers
99 views

Prove by induction that $(x+1)^n - nx - 1$ is divisible by $x^2$

Basis step has already been completed. I've started off with the inductive step as just $n=k+1$, trying to involve $f(k)$ into it so that the left over parts can be deducible to be divisible by $x^2$ ...
0
votes
4answers
95 views

Proof by induction that $ 169 \mid 3^{3n+3}-26n-27$

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
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 ...
2
votes
3answers
42 views

Counting the number of subsets of a set of 2n elements satisfying some conditions.

Let $X =\{v_1, v_2,\cdots, v_n, v_{n+1},\cdots, v_{2n}\}$ be a set of $2n$ elements. I want to find the number of subsets of $X$ with $n$ elements such that both $v_i$ and $v_{n+i} $ are not together ...
2
votes
2answers
85 views

Rebracketing Theorem

My questions regarding the below theorem Both questions are centred on Eq(2) and the paragraph preceding it. 1) How is it that Eq(2) contains $a_k$ but in that section of the proof the assumption is ...
0
votes
0answers
24 views

Proof of propositional logic theorem using Induction on Formulas

How to prove the following theorem using induction on formulas? Let V and V' be two valuations of L. Let $\alpha$ be a formula such that V(p) = V'(p), for all atomic formula p that is subformula ...
2
votes
6answers
92 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
1answer
21 views

Prove that the arithmetic-geometric mean inequality holds for any list of numbers whose length is a power of 2

I am self-studying and currently reading How to Prove it by Velleman. I tried to prove the above by induction (I proved that this holds true for $n=2$), but I think my proof is wrong. I only started ...
3
votes
5answers
186 views

Is this backwards reasoning?

Yesterday I was answering a question on induction: Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear Basically, I was proving a certain formula using ...
1
vote
2answers
44 views

Prove the n-th Fibonacci number is less than $2^n$ for all n greater than zero using strong induction

I need to prove the n-th Fibonacci number is less than $2^n$ for all $n \geq 0$ using strong induction. I have been exposed to the idea that strong induction differs from weak induction in that the ...
1
vote
1answer
77 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
31 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
69 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
21 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 $...
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
32 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
35 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
46 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
64 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
27 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
71 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 ...
0
votes
2answers
60 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
72 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 ...
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
58 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
55 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-...