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

learn more… | top users | synonyms

3
votes
2answers
27 views

Use Induction to prove $\forall m,n \in \Bbb Z_{\ge 0}, 1 +mn \leq (1 + m)^n$

Use Induction to prove: $$\forall m,n \in N, 1 +mn \leq (1 + m)^n$$ for integers $m,n\ge 0$. My biggest problem with this proof is ...
1
vote
0answers
10 views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
6
votes
2answers
65 views

Proof by induction: $(1+x)^n > 1 + nx+nx^2$

This is one of the exercises that appears in Apostol's Calculus I. I'm not sure whether what I did is correct. Let $n_1$ be the smallest positive integer $n$ for which the inequality $(1+x)^n > 1 ...
1
vote
1answer
23 views

Difference Operators

Let $K$ be a field. Given a map $f\colon K\longrightarrow K$, and $h\not=0$ define $\Delta_h f$ to be the map $x\longmapsto\dfrac{f(x+h)-f(x)}{h}$. Then $\Delta_h^j f$ is defined for $j=0,1,2,\dots$. ...
0
votes
4answers
39 views

Does Induction theorem fails here at Euler's conjecture?

I read in a Book written by Raymond A. Barnett and Micheal R. Ziegler the way to prove conjectures for infinite members of a given set and that is, Mathematical Induction. When I read Induction, I ...
1
vote
2answers
26 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
5
votes
5answers
55 views

Demonstration of sum of powers of $2$ [duplicate]

Theorem : For every natural number $p$: $$\sum^p_{i=0} 2^i = 2^{p+1}-1$$ I trieed to demonstrate the theorem using induction Demonstration : $1)$ If we have $p=0$ then we get $2^0=2^{0+1}-1$ that is ...
4
votes
5answers
101 views

Proving a Statement using Mathematical Induction

I'm trying to prove that $6 \mid (n^3 - n)$ where $n$ is a nonnegative integer. I started off by proving the basic step with $P(6)=4$. The next step would be the induction. However I'm having a bit f ...
3
votes
3answers
46 views

Prove this inequality.

Let $S=a_1+...+a_n<1$ where $a_i>0$. Prove that $1+S<(1+a_1)\cdot ... \cdot (1+a_n)<{1\over 1-S}$. I started with the right inequality but I am not sure it iss plausible (I did something ...
1
vote
0answers
24 views

Proving with a given definition that if $|A|=|B|$ then $A,B$ are equivalent (with induction but without using the induction hypothesis)

Let $A,B$ be finite sets, we'll say the sets are equivalent if $|A\setminus B|=|B\setminus A|$. Prove with the above definition that if $|A|=|B|$ then $A,B$ are equivalent. Suppose ...
0
votes
3answers
56 views

Inductive step in proof of Freshman's Dream

I am trying to prove that for $K$ a field of characteristic $p$ prime, $q$ a power of $p$ and $x,y$ in $K$, $$(x+y)^q=(x^q + y^q).$$ I have the base case, and now I am trying to do the inductive ...
3
votes
3answers
56 views

Proving that two summations are equivalent [duplicate]

Give a constructive proof to show that for all $n \geq 1$ , $\sum\limits_{i=1}^n i^3 = (\sum\limits_{i=1}^n i)^2$ Observe that $(n+1)^4 - n^4 = 4n^3 + 6n^2 + 4n + 1$ . Now, the two following ...
2
votes
1answer
24 views

Use induction to show $a_n$ is no greater than $4\log_2(\log_2(n))$

Given a sequence where $a_1 = 1$ and $a_n = 1+ a_{\lfloor\sqrt{n}\rfloor}, n\geqslant 2$. Show that $a_n \leqslant 4\log_2\log_2(n), \forall n \geqslant 3$. Here's my idea: Base case is $n=3, a_3 = ...
1
vote
2answers
39 views

Proof of Binomial Formula Summation - Induction

Let $n\geq 1$ be an integer. Prove that $$ \sum_{k=1}^n k\binom{n}{k} = n\cdot 2^{n-1}. $$ Not sure how to go about doing this question. It says that finding the derivative of $(1+x)^n$ is useful. ...
1
vote
1answer
36 views

Using induction to show associativity on $x_1+\dots + x_n$

I want to use induction to show that the sum $x_1 + \dots + x_n$ of real numbers is defined independently of parentheses to specify order of addition. I know how to apply induction(base, assumption, ...
2
votes
2answers
49 views

Proving with induction $(1-x)^n<\frac 1 {1+nx}$

Prove using induction that $\forall n\in\mathbb N, \forall x\in \mathbb R: 0<x<1: (1-x)^n<\frac 1 {1+nx}$ My attempt: Base: for $n=1: 1-x<\frac 1 {1+x}\iff 1-x^2<1$, true since ...
1
vote
2answers
48 views

Show if $0 \le a <b$ implies $0 \le a^{\frac{1}{n}}<b^{\frac{1}{n}}$

Given that $0\le a<b$ show that $0\leq a^{1/n}<b^{1/n}$ Is this proof by induction? Show it's correct for $n=1$ Assume true for $n=k$, then $0\leq a^{1/k}<b^{1/k}$ holds for some $k$, ...
1
vote
3answers
62 views

Use induction to prove that sum of the first $2n$ terms of the series $1^2-3^2+5^2-7^2+…$ is $-8n^2$.

Use induction to prove that sum of the first $2n$ terms of the series $1^2-3^2+5^2-7^2+…$ is $-8n^2$. I came up with the formula $\displaystyle\sum_{r=1}^{2n} (-1)^{r+1}(2r-1)^2=-8n^2$ but I got ...
0
votes
0answers
11 views

Proof for Determinants using Laplace and induction.

Matrix $A = (a_{ij}) \in M (n x n, Field)$, Matrix $B = ((-1)^{i+j}a_{ij})$ I need to prove that det(A)=det(B). I thought induction might be one solution, but I don't know how to apply the Laplace ...
1
vote
2answers
39 views

Induction proof concerning Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$, together with $p_0 = 0$ and $p_1 = 1$. Prove with ...
0
votes
1answer
21 views

summation inequality with logarithms

show: $$\sum_{i=1}^n \log_{2}\,i = O(n\log n)$$ Proof by induction: $$\sum_{i=1}^n \log\,i \le n\log n$$ $$\text{Test for n=1: }\sum_{i=1}^1 \log_{2}\,i \le 1\log 1$$ $$0 \le 0\text{ true for ...
3
votes
1answer
82 views

How is induction justified in intuitionistic logic?

This question might be extremely naïve for which I apologise in advance. The induction principle can be stated as: If $A ⊂ ℕ$ such that $1 ∈ A$, and $ν(A) ⊂ A$ (where $ν\colon ℕ → ℕ$ is ...
0
votes
1answer
37 views

For what natural number $n$ is the following inequality true: $2^n \geq 2\cdot n^2$?

Can you solve this by using induction? The inequality is true for $n = 1$, but is false until $n = 7$. After the induction step I got $$2^n \geq n^2 + 2n + 1.$$ If you take the limit as $n$ ...
0
votes
0answers
19 views

Practicing mathematical proofs in preparation for another course and could use some help [closed]

I'm starting a course on Algorithms and the professor wants to test our induction and proof knowledge. Problem is, our prerequisite courses never focused on such material. I'm hoping someone could ...
3
votes
1answer
57 views

Proof that $\sum_{i=1}^n{1} = n$ for all $n \in \Bbb Z^+$

It seems obvious that $$\forall n \in \Bbb Z^+, \sum_{i=1}^n{1} = n $$ However, I'm having trouble coming up with a formal proof for this. Given a concrete number like $4$, we can say that ...
1
vote
1answer
12 views

Power of two commuting elements in a group is the binary operation of each of the two elements raised to that power

Let $(G,\ast)$ be a group and let $n\in\aleph$. Prove that if g, h $\in G$ commute, then $(g\ast h)^n$=$g^n\ast h^n$
0
votes
1answer
26 views

Proving the existence of a Bijection between Cartesian Products of Sets by Induction

Prove by induction that for any sets $A_1, \ldots , A_n$, there is a bijection from $(((A_1 \times A_2) \times A_3) \times \ldots \times A_n)$ to $A_1 \times (A_2 \times ( \ldots (A_{n-1} \times A_n) ...
0
votes
2answers
30 views

proof by induction summation inequality

show by induction that: $$\sum_{i=1}^n i^2 = O(n^3)$$ what I have so far: $$\sum_{i=1}^n i^2 <= n^3$$ base case: for n=1 $$\sum_{i=1}^1 i^2 <= 1^3$$ ...
0
votes
1answer
13 views

Cantor Set and Base 3 Decimal Expansions

I'm trying to show that every point in the Cantor Set (obtained by "middle-thirds" removal, starting with $[0,1]$) has a base 3 decimal expansion consisting of only zeros and twos. I think the proof ...
1
vote
1answer
12 views

Proof via strong induction of a string output

I'm still new to the whole proof thing (first class of discrete mathematics and analysis right now). I could do general induction problems, but the fact that 'n' is the output here along with the ...
1
vote
1answer
28 views

Proof of the second principle of mathematical induction

This was an exercise in my lecture notes for which no answer was provided, so I seek verification on whether my proof is correct. Prove that if 1. $P(n_0)$ is true for some $n_0 \in \mathbb N$, and ...
1
vote
1answer
25 views

Inverse of a product in a group can be written as the product of the inverses of each element in reverse order

Let $(G,\circ)$ be a group and let $g_1,...,g_n\in G, n\in\aleph$. Prove that $(g_1\circ ...\circ g_n)^{-1}=g_n^{-1}\circ ...\circ g_1^{-1}$ I tried this by induction but was unsure how to take out ...
0
votes
1answer
43 views

prove by mathematical induction

I've been trying to solve this but I'm having trouble in simplifying it, in order to match the right hand side. Could you solve this? $$\sum_{i=1}^{n+1} i\cdot 2^i = n\cdot 2^{n+2} +2 ,$$ for all ...
0
votes
3answers
77 views

Proof of an inequality by induction

Let $n \in \mathbb N^+$. Show that if $x_1, x_2, ... , x_n$ are $n$ real numbers such that $-1 \le x_i \le 0$ for each $1 \le i \le n$, then $$(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + ...
3
votes
2answers
35 views

Proving $1+\sum_{i=1}^n i (i!)=(n+1)!$ [duplicate]

How would you prove the following using induction. n is a non negative integer $$1+\sum_{i=1}^n i i!=(n+1)!$$ This be what I did base case let $n=3$ $$1+1+4+18=(3+1)!$$ $24=24$ Hypothesis step ...
2
votes
1answer
23 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
3
votes
1answer
44 views

How to prove that calculating Ackermman function stops?

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ be Ackermann function. How to prove by structural induction ...
0
votes
0answers
18 views

What is the difference between assuming for $\forall k< n$ and proving for $n$ than assuming for $n$ and proving for $n+1$

What is the difference between assuming for $\forall k< n$ and proving for $n$ than assuming for $n$ and proving for $n+1$ (or $n-1$ and proving for $n$)? both with induction. The first one is ...
2
votes
3answers
55 views

Proof by induction, binomial coefficient

I have to make the following proof: $${\sum\limits_{k=1}^n}{k}{n\choose k} = n2^{n-1}$$ Base case, $n = 1$: $${\sum\limits_{k=1}^{1}}{k}{1\choose k} = 1 = 1\cdot2^0=1$$ Inductive Hypothesis: for ...
0
votes
4answers
48 views

I'm having trouble understanding a step of induction.

The problem my teacher presented was to prove, $(1 + x)^n \geq 1 + nx$ for all real numbers $x > -1$ and integers $n \geq 2$. The way it was done in class is: $(1+nx)(1+x) ≤ (1+x)^n (1+x) $ ...
-1
votes
1answer
24 views

Ordering of real numbers compatible with n-th powers/reciprocal powers (induction)

I have to use induction to prove that $$0 \leq a < b \implies 0 \leq a^n < b^n$$ for all natural n. Also (perhaps very similarly) that $$0 \leq a < b \implies 0 \leq a^{1/n} < b^{1/n}.$$ ...
1
vote
5answers
123 views

how to prove: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ [duplicate]

need help to prove this: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ where $n$ is integer $\geq 1$. Question also said taking the derivative of $(1 + x)^n$ would be helpful which I've found ...
5
votes
2answers
84 views
+100

Fascinating induction problem with numerous interpretations

Problem: Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile, ...
0
votes
1answer
21 views

Two recurrence relations gcd proof

Let $q_1, q_2,\ldots$ be a sequence of integers with $q_i\gt0$ for all $i\gt 1$. Define $(a_n)_{n\ge-1}$ and $(b_n)_{n\ge-1}$ by the following recurrence relations: $a_{-1}=0,\ a_0=1,\ b_{-1}=1,\ ...
0
votes
3answers
44 views

simple proof by induction exercise - beginner [duplicate]

I am rather illiterate when it comes to mathematics, I am afraid. In an effort to change that, I grabbed a copy of 'What is mathematics? : An elementary approach to ideas and methods' and have already ...
0
votes
2answers
42 views

Trouble solving this induction problem

Show that, for every $n\ge2$, $3^n >n(n-1)$. Well, I started by showing the base case ($n = 2$): $3^2 > 2$ Now, for $n+1$: $P(n)\Rightarrow P(n+1)$ $$3^{n+1} > (n+1)n$$ My ...
0
votes
1answer
45 views

proof of the negative binomial series using induction?

$$(1-x)^{-n} = \sum_{k\ge0}{k+n-1 \choose n-1}x^k$$ I'm supposed to prove this for any integer n $\ge$ 1 via induction on n. Base case where n = 1 is easy enough to prove, but what about the ...
1
vote
7answers
50 views

Induction proof of $1 + 6 + 11 +\cdots + (5n-4)=n(5n-3)/2$

I need help getting started with this proof. Prove using mathematical induction. $$ 1 + 6 + 11 + \cdots + (5n-4)=n(5n-3)/2 $$ $$ n=1,2,3,... $$ I know for my basis step I need to set $n=1$ but I ...
1
vote
1answer
20 views

Bernoulli's inequality variation

To prove: $(1+a_1)(1+a_2)\ldots(1+a_n)\geq\dfrac{2^n}{n+1}(1+a_1+a_2+\ldots+a_n)$ when $a_i\geq1$ This seems to be based on Bernoulli's Inequality (which can be proved by induction). Trying the ...
0
votes
2answers
49 views

If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$

Suppose that $k$, $n$, and $d$ are integers and $d$ is not $0$. Prove: If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$. You may not use the theorem stating the following: Let ...