Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

1
vote
3answers
406 views

Using mathematical induction

I'm reading from my book about mathematical induction, and there is an example that says "Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps" let ...
3
votes
3answers
62 views

Strong induction doesn't require a base case?

I'm considering the natural numbers to be the nonnegative integers. The principle of strong induction can be stated as follows, "If $P$ is a property such that for any $x$, if $P$ holds for all ...
6
votes
2answers
63 views

How do you prove $n! \leq (n/2) ^n$?

I'd be really grateful if someone could help me figure out how you prove $n!\leq (n/2) ^n$ ?
0
votes
2answers
45 views

Fibonacci Recursion Equation

For the Fibonacci sequence, prove the formula $a^2_{n+1} = a_n a_{n+2} + (-1)^n$ using induction. I have done the base case, when $n=3$, because for the Fibonacci sequence, $a_1=a_2=1$. I have no ...
3
votes
4answers
165 views

How can I show that $4^{2n}-1$ is divisible by $15 $ for all $n$ greater or equal to $1$

Ok so this is a question from a book that has no included solution and I think I'm on the right way but I just need a little help. The question is: Show, for all $n \ge 1$ such that $4^{2n} - 1$ ...
2
votes
3answers
143 views

Induction: $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt n}}} < 3$ [duplicate]

I'm trying to prove that $$ \sqrt{2\sqrt{3\sqrt{4\cdots\sqrt{n}}}} < 3 $$ for any $n$ and have decided to use strong induction and instead just show that $$ \sqrt{k\sqrt{(k + 1)\cdots\sqrt{n}}} ...
3
votes
5answers
98 views

Induction: $n + 3 < n!$ for all $n>3$

I have a proof that I am trying to prove and I am getting stuck at the inductive hypothesis. This is my theorem: For all real numbers $n>3$, the following is true: $n + 3 < n!$. I have ...
1
vote
0answers
63 views

How to use an exponent that contains a variable

I am trying to understand a problem that uses mathematical induction to prove the validity of a statement. This is how one section moves to another: $$ 2k + 3 = 2^{k + 1} $$ $$ 2k + 3 = (2k + 1) + 2 ...
1
vote
2answers
86 views

Prove by induction that $1^3 + 2^3 + 3^3 + …+ n^3= \frac{n^2(n+1)^2}{4}$ for all $n\geq1$. [duplicate]

Use mathematical induction to prove that $1^3 + 2^3 + 3^3 + .....+ n^3= \frac{n^2(n+1)^2}{4}$ for all $n\geq1$. Can anyone explain? Because I have no clue where to begin. I mean, I can show that ...
3
votes
3answers
96 views

Can $(1-\frac{1}{2})(1-\frac{1}{2^2})(1-\frac{1}{2^3})…(1-\frac{1}{2^{n-1}})(\frac{1}{2^n})$ be simplified?

Can $(1-\frac{1}{2})(1-\frac{1}{2^2})(1-\frac{1}{2^3})...(1-\frac{1}{2^{n-1}})(\frac{1}{2^n})$ be simplified? It seems like an expression from a simple induction proof problem that's missing its ...
2
votes
2answers
180 views

basic induction probs

Hello guys I have this problem which has been really bugging me. And it goes as follows: Using induction, we want to prove that all human beings have the same hair colour. Let S(n) be the ...
2
votes
2answers
251 views

Proof by Induction Question with regard to the Knight's Tour

I have to prove that the formula $4n^2-12n+8$ gives the number of edges on a knight graph, where n is the number of vertices horizontally and vertically and n^2 is the number of vertices. I've proved ...
4
votes
4answers
188 views

Prove $3^n \ge n^3$ by induction

Yep, prove $3^n \ge n^3$, $n \in \mathbb{N}$. I can do this myself, but can't figure out any kind of "beautiful" way to do it. The way I do it is: Assume $3^n \ge n^3$ Now, $(n+1)^3 = n^3 + ...
1
vote
1answer
59 views

Strong explanation of Strong Form of Mathematical Induction

I don't quite understand induction well, and was wondering if you could explain to me what induction is and what the strong form of induction is.
0
votes
1answer
470 views

proof by induction analysis

Consider the following description of a game. There are $n$ people playing, one of whom leads the game. They are playing on a playing field with no obstacles. Everyone carries one water balloon. ...
0
votes
0answers
25 views

Discrete Math Equation Proof (by induction?) [duplicate]

Consider the following description of a game. There are n people playing, one of whom leads the game. They are playing on a playing field with no obstacles. Everyone carries one water balloon. ...
2
votes
1answer
73 views

Prove a sum of sequence: Discrete math and weak induction

The problem is as follows: Prove that $2 - (2\cdot7) + ((2\cdot7)^2) - ... +(2(-7))^n = > \frac{(1-(-7)^{(n+1)})}{4}$ whenever $n$ is a non-negative integer. Our book is asking for a basic ...
10
votes
1answer
115 views

Minimum number of hemispheres covering a sphere

Here is a question which seems easy but seems to have many pitfalls. If I give you an arbitrary covering of the sphere by $N$ closed hemispheres. You can pick any of the hemispheres to keep. What is ...
0
votes
2answers
300 views

Proof by strong induction [closed]

Consider the sequence: $$a_0=1, a_1=2, a_2=3; \,\, a_k=a_{k-1}+a_{k-2}+a_{k-3}, \, k \geq 3,$$ and the statement $P(n):a_n \leq 2^n$. Prove $\forall \, n \in \mathbb{N}, \, P(n)$. ($\mathbb{N}$ ...
1
vote
1answer
112 views

Induction over negative number

Suppose I were given the task of proving that for all negative integers $3n^{2} \equiv 3n \pmod{6}$. The original intent was to use negative induction. But, I was wondering if another, perhaps simpler ...
4
votes
1answer
87 views

Proof with mathematical induction

Proof with mathematical induction. I have the following induction problem: $ (\frac{n}{n+1})^2 + (\frac{n+1}{n+2})^2 + ... + (\frac{2n - 1}{2n})^2 \le n - 0.7 $ This property applies to all $n \ge ...
3
votes
3answers
79 views

How to prove the inequality $\sum_{i=1}^n \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{n}}{2} $ for $n\in\mathbb{Z}^+$?

I have to prove this inequality: $$ \forall n \in Z^+, \sum_{i=1}^n \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{n}}{2} $$ So far, I have done the base cases and assumed the inequality is true for some ...
0
votes
1answer
96 views

Strong induction definition clarification

I have a general question about strong induction: Assuming that the base case is 0, if I let my inductive hypothesis be that for all 0 <= k < n some statement is true, and if I prove that that ...
2
votes
1answer
169 views

Question: Prove that a set of connectives is incomplete using structural induction

The proof generally begins with an inductive definition of the set. For example, let's say the set of connectives was {$\oplus$}. Let F be the smallest set such that: 1) Any propositional variable is ...
4
votes
1answer
60 views

Inductive definition with choice for sequence

In topology there is a very common way to define a sequence. This usually go something like: "Define $\{z_{n}\}$ to be a sequence such that $z_{0}$ is <blah blah blah>, and $z_{n}$ is such that ...
1
vote
2answers
42 views

Induction with sets: $\forall n \ge 1: \overline{\bigcap_{i=1}^nA_i}=\bigcup_{i=1}^n \overline{A_i}$

I know how to do induction with equations, but for this thing with sets: $$\forall n \ge 1: \overline{\bigcap\nolimits_{i=1}^nA_i}=\bigcup\nolimits_{i=1}^n \overline{A_i}$$ exactly I don't have an ...
6
votes
6answers
1k views

Proof that $\int_0^{2\pi}\sin nx\,dx=\int_0^{2\pi}\cos nx\,dx=0$

Prove that $\int_0^{2\pi}\sin nx\,dx=\int_0^{2\pi}\cos nx\,dx=0$ for all integers $n \neq 0$. I think I'm encouraged to prove this by induction (but a simpler method would probably work, too). ...
0
votes
1answer
148 views

Prove that set is countable? [duplicate]

Show that the set N* of finite sequences of nonnegative integers is countable. Where do I start? I think I have to prove that there is a bijection between N* and N (set of natural numbers), but how ...
-1
votes
3answers
121 views

Prove $2^n > 10n^2$ for all sufficiently large integers n.

How do I prove $2^n > 10n^2$ inductively? I know you can prove this to be true using calculus (i.e. taking derivatives). But how would I do it inductively?
0
votes
2answers
88 views

How to prove that a series is equal to a recursive algorithm

I have the following sequence: $$ y_n = \int_0^1 \frac{x^n}{x+5}\,dx, n = 0,1,\dots $$ Now I have the following recursive algorithm: $$ y_0 = \log{6} - \log{5} $$ $$ y_n = \frac{1}{n} - 5y_{n-1}, n ...
2
votes
2answers
66 views

Basic Proof By Induction, Assistance Required

With the following question. Is it better to start the proof by proving it for n=0, n=1 or both? Once I've done that, I prove it for n=p where p is any integer equal to or greater than 0. For the ...
0
votes
1answer
46 views

Generalized Bernoulli's inequality

I was able to prove Bernoulli's inequality, easily by simple induction. However, I'm not sure how to prove the generalized inequality (generalized = for each sequence of numbers i=1..n): ...
0
votes
1answer
81 views

Prove by induction on strings

I have this question: Prove by induction on strings that for any binary string w, (oc(w))^R = oc(w^R). note: if w is a string in {1,0}*, the one's complement of w, oc(w) is the unique string, of ...
2
votes
2answers
3k views

Proof by Induction for a recursive sequence and a formula

So I have a homework assignment that has brought me great strain over the past 2 days. No video or online example have been able to help me with this issue either and I don't know where to turn. I’m ...
1
vote
2answers
690 views

Prove: Dividing an odd number by 2 always produces a remainder of 1

How would I go about proving that for all n belonging to the natural numbers, if any given odd number n is divided by 2, then the remainder is at least 1? I got a hint: Try to reduce the number of ...
2
votes
2answers
65 views

How do I prove that $(1+\frac{1}{2})^{n} \ge 1 + \frac{n}{2}$ for every $n \ge 1$?

How do I prove that $(1+\frac{1}{2})^{n} \ge 1 + \frac{n}{2}$ for every $n \ge 1$ My base case is $n=1$ Inductive step is $n=k$ Assume $n=k+1$ $(\frac{3}{2})^{k} \times \frac{3}{2} \ge (1 + ...
0
votes
1answer
176 views

Discrete mathematics simple/strong induction

Consider the sequence: $a_0 = 1; a_1 = 2; a_2 = 3; a_k = a_{k-1} + a_{k-2} + a_{k-3}; k \geq 3$ and the statement $P(n) : a_n \leq 2^n$. Prove that $\forall n \in \mathbb{N}$, $P(n)$ holds. I would ...
1
vote
1answer
113 views

Trying to understand an exercise using factorials with induction

Exercise: Prove that (n + 1)! - n! = n(n!) for any n $\ge$ 1 Given Answer: I will skip the basic step since I understand that part. (n + 2)! - (n + 1)! = (n + 1)!(n + 2) - n!(n + 1) I understand ...
0
votes
1answer
45 views

Need Help Solving Polynomial Equation

I'm working on an induction problem that basically boils down to this equation: $$2(-1)^k+ 6(2^k)\left(-\frac{1}{2}\right)^{k+1} + (-1)^{k}=0$$ I'm fairly confident that the equation above is the ...
2
votes
2answers
209 views

Prove by mathematical induction: $n < 2^n$

Step 1: prove for $n = 1$ 1 < 2 Step 2: $n+1 < 2 \cdot 2^n$ $n < 2 \cdot 2^n - 1$ $n < 2^n + 2^n - 1$ The function $2^n + 2^n - 1$ is surely higher than $2^n - 1$ so if $n < ...
3
votes
3answers
96 views

Integers whose sum and product are integers

Let $a$, $b$ be real numbers such that $a + b$ and $ab$ are integers. a. Prove that $a^n + b^n$ is an integer for every natural number $n$. b. Suppose that $a$ does not equal $b$. Prove that ...
1
vote
1answer
80 views

Prove by induction the following inequality for all n∈N [duplicate]

$\frac1{\sqrt{1}} + \frac1{\sqrt{2}}+\frac1{\sqrt{3}}+...+\frac1{\sqrt{x}}\ge {\sqrt{x}}$ I proved the basic case: and realize it is equal to 1, but I have absolutely no idea how to create prove the ...
0
votes
1answer
31 views

Inductive proof for all naturals (including 0), x, starting from one of two given starting points

The given starting points for this inductive proof are the following: 1) the formulas, G(2x-2) = G(x)^2 - G(x-2)^2 and, G(2x-1) = G(x+1)G(x) - G(x-1)G(x-2) or ...
0
votes
2answers
120 views

fill-in-the-blank induction proof

I'm stuck at homework task I'm working on. I would really appreciate some help. Here is the task: Let $f$ be a function on binary numbers defined recursively as follows. $f(0) = 1$ and ...
0
votes
2answers
110 views

Prove that $1^2 + 3^2 + 5^2+\cdots+(2n-1)^2 = (4n^3-n)/3$ for all $n \in \mathbb{N}$

Prove that $1^2 + 3^2 + 5^2+\cdots+(2n-1)^2 = (4n^3-n)/3$ for all $n \in \mathbb{N}$. How can I solve this with induction? I've been working through a couple examples and for this one I can't relate ...
3
votes
2answers
138 views

Tallest bubble tower induction proof

A hemispherical bubble is placed on a spherical bubble of radius $1$. A smaller hemispherical bubble is then placed on the first one. This process is continued until $n$ chambers, including the ...
1
vote
3answers
83 views

Prove a formula in terms of n:

$1+5+9+...+(4n+1)$ I HAVE to use induction, but I am new to induction, so I am a bit confused... I believe I have to use the base case first: so $n=1$ is $4(1)+1=5$, but i get the second term in the ...
1
vote
2answers
63 views

Trouble understanding induction on two integer variables

I am trying to understand induction on two integer variables Induction on two integer variables Let's take this case: $P(0,0)$ $\forall x,y. P(x,y) \Rightarrow P(x+1,y)$ $\forall x,y. P(x,y) ...
0
votes
1answer
75 views

Prove by strong induction a “recursive algorithm” form of the 5th Peano axiom

The given recursive algorithm is as follows: If an algorithm $P$ has one argument $n$ of type natural, it terminates when called with the argument $0$. When called with an argument $x > 0$, it ...
0
votes
1answer
32 views

Induction proof of $a^r \ge 1$

I understand induction with one variable well, however I am not sure what to do when there are 2 or more variables. The problem I came across is following: Prove that $a^r \ge 1$, where $r \in ...