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
74 views

How to prove that $9^n - 8n - 1$ is divisible by $64$ for $n\ge 0$?

My textbook provided the following proof: Base case: When $n=0, 9^n-8n-1=0=64\cdot0$, so $64\mid\left(9^n-8n-1\right)$. Induction step: Suppose that $n\in\mathbb N$ and ...
1
vote
2answers
17 views

Help with induction step of proving a recursive definition / sequence

I'm a bit of a maths noob so please bear with me with what is probably a really dumb question, but I could really do with some help - I'm self-learning at home. I'm stuck on the question below from ...
0
votes
2answers
66 views

The necessity of the axiom of induction

$\underline{First\ question}$ Let $P(n)$ be a proposition about $n$. In standard mathematical induction, we require: (1)$P(0)$ holds. (2)If $P(n)$ holds, $P(n+1)$holds. Here we use "the axiom of ...
1
vote
1answer
71 views

How do I use the principle of mathematical induction to prove whether or not $\sum_{k=1}^n (-1)^k = \frac{(-1)^n-1}2$ is a true statement?

For all n elements of Natural Numbers,$\sum_{k=1}^n (-1)^k= \frac{(-1)^n-1}2$. I proved p(1) to be true : $\sum_{k=1}^1 (-1)^k = (-1)^1 =-1$. And $\frac{(-1)^1-1}2 = \frac{(-2)}2 = -1$ So P(1) ...
0
votes
3answers
49 views

Use mathematical induction to prove $ (2n)!\geq 2^n(n!)^2$ for $n \in \mathbb{N}$

I am trying to use mathematical induction to prove $$(2n)!\ge2^n(n!)^2\quad\text{for }n\in\mathbb{N}$$ I am stuck at the $n=k+1$ point.
0
votes
1answer
23 views

Proving that there exists a horizontal chord with length $1/n$ for a continuous function $f: [0,1] \to \mathbb R$

Given a continuous function $f: [0,1] \to \mathbb R$ and that the chord which connects $A(0, f(0)), B(1, f(1))$ is horizontal then prove that there exists a horizontal chord $CD$ to the graph $C_f$ ...
8
votes
1answer
56 views

Is there a standard name for this “continuous induction” principle?

I am working on a paper, and I want to prove that some statement $P(x)$ holds for every value of a parameter $x \in [0,\infty)$. I plan to proceed as follows: Show that $P(0)$; Show that if $P(x)$ ...
3
votes
6answers
79 views

Using induction prove $(n^3)-n$ is divisible by 3 whenever n is a positive number.

I am not sure if I am doing this right, but I have this: There exists an integer $k$. $2k =$ positive number $(2k)^3 - 2k$ [*And this is where I get lost. How does one prove this?]
0
votes
0answers
61 views

Why is $y + 1$ infinite?

This is related to SO question : http://stackoverflow.com/questions/30150877/why-does-this-cause-ghci-to-hang but I'm having difficulty understanding why Haskell enters an infinite loop but since ...
3
votes
8answers
111 views

Proving that $12^n + 2(5^{n-1})$ is a multiple of 7 for $n\geq 1$ by induction

Prove by induction that $12^n + 2(5^{n-1})$ is a multiple of $7$. Here's where I am right now: Assume $n= k $ is correct: $$12^k+2(5^{k-1}) = 7k.$$ Let $n= k+1 $: $$12^{k+1} + 2(5^k)$$ ...
3
votes
2answers
42 views

simplifying equations

I have been trying to study analysis of algorithms with mathematical induction yet I found my algebra skills are very poor. So now I began restuddiing algebra (factoring, destributive property, ...
3
votes
3answers
37 views

Prove that Euclid's algorithm computes the GCD of any pair of nonnegative integers

I've been struggling with a basic exercise involving Euclid's algorithm and mathematical induction. Given the following definition of the Euclid's algorithm (in Java): ...
1
vote
1answer
33 views

How to show $(1+a)^n<1+2^n a$ for all $n\in\mathbb N$ and $a\in (0, 1)$?

There is an induction problem which is baffling me. I'm supposed to use induction to show the inequality $$(1+a)^n< 1+2^n a,$$ for all $n\in\mathbb N$ and $a\in (0, 1)$. I guess there must be some ...
1
vote
0answers
44 views

How to teach Mathematical Induction mathematically? [migrated]

I am exhausted of teaching Mathematical induction to my little brother. I have given him many examples, Domino effect, aligned shops of hot dogs etc and every time he says that he got it but when I ...
0
votes
1answer
48 views

Show that there exists a unique function with a certain property

I'm trying to prove the following theorem: "Let $~f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}~$ be a function, and let $~c~$ be a natural number. Show that there exists a unique function $~a: ...
0
votes
2answers
29 views

Using induction prove $\sum\limits_{k=1}^n\dbinom{k}{k-1}$=$\binom{n+1}{n-1}$

$\sum\limits_{k=1}^n\dbinom{k}{k-1}$=$\binom{n+1}{n-1}$ We are supposed to use induction to prove this inequality. After the base case, I tried to use the definition $\binom{n}{k} = ...
8
votes
6answers
247 views

Proof without using induction [duplicate]

How to prove that $$1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$ without using induction. If we don't know the right side of this expression, how to get right expression. I tried with partial sums and ...
2
votes
1answer
51 views

how to prove by induction the $ (1+x)^{n}>1+nx+nx^2$

Prove by induction the formula $ (1+x)^{n}>1+nx+nx^2$ for $x>0$ real number and $n\ge 3$ my try : multiply both sides by $(1+x)$ gives $ (1+x)^{n+1}>1+(n+1)x+(2n+nx)x^2$ have I done ...
1
vote
2answers
68 views

Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$

Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$ where $\{x_k\}_1^n$ are real numbers which are not all the same. I tried to prove it by induction. ...
1
vote
2answers
31 views

Is this inductive big O proof possible / Does this question make sense?

Prove that $\sum_{i=j}^k \frac 1i$ is $O(\ln(k)-\ln(j-1))$ using induction for all $i$. The way I understand this question, it's nonsense - $i$ is the iteration variable, not something that can be ...
0
votes
1answer
30 views

How to prove this by induction

Prove by induction the following equality : $\ 1-4+9-16+\cdots+(-1)^{n+1} n^2 = (-1)^{n+1}(1+2+3+\cdots+n) $ I don't know what to do in this case, I know what to do in general but can do this one
1
vote
3answers
37 views

Question regarding proving by induction

I am struggling with a math problem I have been assigned. The problem is as follows: Let $X_1 = -3$ and $X_2 = 0$. Given that for every natural number $n \geq 2, X_{n+1} = 7X_n - 10X_{n-1}$, prove by ...
5
votes
1answer
52 views

Partition onto subsets at the same sum

Positive integers $ a_1, a_2,\ldots, a_n $ such that $ a_k\leq k $ and the sum of all these numbers is even and equal to $ 2S $. Prove that the number can be divided into two groups, the amount of ...
0
votes
2answers
68 views

Using induction to prove letter arrangement

There are n letters written to different people, and envelopes correspondingly addressed. The letters are mixed before being sealed in envelops, the effect being to make n!allocations of letters to ...
4
votes
8answers
152 views

Proving that $5^n-1$ is divisible by $4$ for $n\geq 0$ by induction

I hope this is not counted as a duplicate, as I would like to know if my proof is valid: $P(n): 5^n - 1$ is divisible by $4$ for $n \ge 0$. Base Step: $P(0): 5^0-1 = 1-1 = 0 = 0\times 4$. Induction ...
-1
votes
2answers
76 views

What are the prerequisites required if I have to do induction to prove a certain theorem

I have always been fascinated by mathematical induction. The idea of induction is itself such a great analogy. But sometimes induction makes me feel that it is very messy. My professor keeps on saying ...
0
votes
4answers
41 views

Show that the sequence is monotone and bounded.

Show that the sequence defined by $a_1=1$ and $a_n=\sqrt{3+a_{n-1}}$ for $n>1$ is monotone and bounded. Then find the limit of the sequence. I'm supposed to do this using induction. I'm usually ...
1
vote
3answers
62 views

How to prove a Fibonacci inequality using Strong Induction?

Using strong induction I am trying to prove that $$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$ for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n ...
1
vote
1answer
36 views

Induction Clarification

I had this problem: Is it always necessary to go from n to (n + 1) or from (n - 1) to n in the inductive hypothesis? Is the "direction" always important? Here is my solution to one such proof, which ...
1
vote
2answers
58 views

How to prove that the statement $ 4+10+16 + \cdots + (6n-2) = n(3n+1)$ for all $n \ge 1$ using mathematical induction?

I know you begin by establishing that it is true for $n=1$ which gives $6(1)-2 = 1(3\cdot1\cdot+1)$. Then I replace each $n$ for a $k$, and I suppose that is true for $6k-2=k(3k+1)$. But then the ...
2
votes
0answers
45 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
3
votes
2answers
65 views

Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$

Solve the following recurrence relation: $$\begin{align} S(1) &= 2 \\ S(n) &= 2S(n-1) + n 2^n, n \ge 2 \end{align}$$ I tried expanding the relation, but could not figure out what the closed ...
1
vote
2answers
67 views

Proving $n^2≤2^n+1$ for $n\geq 1$ by induction

Prove $n^2\leq 2^n+1$ for $n\geq 1$ using induction. Proof. For $n=1, (1)^2\leq 2^1+1=3$. $\therefore 1\leq 3$ is true. Assume $n=k$ is true so $k^2\leq 2^k+1$ or $k^2-1\leq 2^k$. Then prove for ...
4
votes
5answers
139 views

Inequality in Algebra: $1 \leq x_1 x_2 \cdots x_n$ implies that $2^{n} \leq (1 + x_1)(1+x_2) \cdots (1 + x_n).$

How do I prove that if $x_1, \ldots, x_n$ are positive real numbers, then $$1 \leq x_1 x_2 \cdots x_n \text{ implies that } 2^{n} \leq (1 + x_1)(1+x_2) \cdots (1 + x_n).$$ I attempted a proof by ...
1
vote
2answers
69 views

Confusion about how to prove $\sum_{i=0}^n 2^i = 2^{n+1}-1$ for all $n\geq 0$ by induction

I'm trying to understanding proof by induction. But how do I check if that is correct? How do I know what I need to show? Any help would be great. Just trying to get my head around this. So I have ...
0
votes
2answers
39 views

Strong Induction

Define a recursive sequence $a_0$, $a_1$, $a_2$, . . . by $a_0 =1$,$a_1 =3$, $a_n$ = $2a_{n−1}$ + $8a_{n−2}$ for all integers $n≥2$ Prove by strong induction that $a_n$ $≤ 4^n$ for all integers $n ≥ ...
1
vote
3answers
80 views

Show that the sequence defined recursively by $a_{n+1} = \sqrt{3a_n + 1}$ is increasing

Assume that the sequence ${a_n}$ is defined recursively by $a_{n+1} = \sqrt{3a_n + 1}$ for all $n \in \mathbb N$, with $a_1 = 1$. Use mathematical induction to prove that $a_n \leq a_{n+1}$ for all ...
1
vote
1answer
35 views

Proving Inequality using Induction.

I am trying to prove the following statement: For every nonnegative integer $n$, $1+6n \le 7^n$. I did the base case where $n=0$ but am having trouble manipulating the inductive step. So far I ...
1
vote
2answers
27 views

How do I prove this with induction?

I am give $a_{n+1}=\sqrt{a_{n}+12}$ and $a_{n}∈[-12, 4]$. I need to prove $0≤a_{n}≤4$ for all $n≥2$. I have that $a_{2}∈[0,4]$ so it works for the first case and $a_{3}∈[\sqrt{12},4]$ so it holds for ...
0
votes
0answers
37 views

Solving a general system of linear equations

We are given a system with n linear equation: $$\forall i\in \{1,...,n\}: i \cdot x_i + \sum_{j=i+1}^{n}x_j= \frac{i}{n}$$ Prove that the solution for this system of equation is $$\forall i\in ...
2
votes
1answer
32 views

Understanding an application of induction in a proof

I understand what is done below, however I don't understand the induction used, especially not when applying $0\leq n$. If $s_n+1=f(s_n)$ with $|f′(x)|\leq 1/2$ prove that the sequence $s_n$ ...
-1
votes
3answers
94 views

Use mathematical induction to prove a statement [closed]

Use mathematical induction to prove that: $$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$
0
votes
2answers
24 views

Help with solving mathematical induction problem

I need help with the following: Use mathematical induction to prove that for every $n\in N$, $$ \sum_{k=1}^n\frac{1}{\cos kx \cos(k+1)x}=\frac{\tan(n+1)x-\tan x}{\sin x} $$ For $n=1$, the statement ...
0
votes
2answers
63 views

Prove for integers $a,b\ge 3$ that $a^2+b^2+1>(a+1)(b+1)$

Prove for integers $a,b\ge 3$ that $a^2+b^2+1>(a+1)(b+1)$. Original question asked for positive real solutions, but I've changed it to integers. It's question I've come up with. AM-GM ...
2
votes
3answers
46 views

Can mathematical inductions work for other sets?

I know that induction works only for the natural numbers $\mathbb{N}$. We first have to prove the base case. And we then prove that if the statement $p(k)$ holds then $\color{blue}{\textbf{p(k+1)}}$ ...
3
votes
2answers
48 views

Proof By Contradiction [?]

There are $n$ islands with $n$ bridges connecting pairs of islands (where $n\ge 2$). Prove that some sequence of distinct bridges forms a loop. __ Since it isn't obvious how to prove it directly I ...
2
votes
3answers
195 views

How to prove a sum of series

How do I prove that for any natural number $n$ we have $$\sum_{i=0}^n i^4 \neq \left(\sum_{i=0}^n i\right)^3?$$ Any help would be greatly appreciated.
-1
votes
1answer
27 views

Help with a demonstration with triangle numbers

Recently I've been doing some work with trianglular numbers. Basically I wanted to show that for every nth triangular number $T_n$ $$T_n=\frac{n(n+1)}2$$ For me the simplicity if this equation is ...
6
votes
4answers
109 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
2
votes
2answers
27 views

Help with Factorial Inequality Induction proof

So I'm asked to prove $3^n + n! \le (n+3)!$, $\forall \ n \in \mathbb N$ by induction. However I'm getting stuck in the induction step. What I have is: (n=1) $3^{(1)} + (1)! = 4$ and $((1) + 3)! = ...