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

Induction Proof (relating two recurrences)

Let $L(n) = n + 2 L\left(\frac{n}{2}\right), \, L(1) = 1,$ and $U(n) = 9n + 2U\left(\frac{n}{2}\right), \, U(1) = 9.$ Prove by induction that $U(n) = 9L(n)$ where $n = 2^k$. I attempted to prove ...
2
votes
1answer
169 views

DFA Transition Function Inductive Proof

Show for any state $q$, string $x$, and input symbol $a$, $\hat\delta(q, ax) = \hat\delta(\delta(q, a), x)$, where $\hat\delta$ is the transitive closure of $\delta$, which is the transition function ...
1
vote
3answers
85 views

Mathematical induction… divisible by 4

Hello I need to proof that the expression $(9^{n}+3)$ is divisible by $4$. It is true if I calculate it for $n=1$ for $n + 1$ I got stuck in here: $9 \cdot 9^n + 3$ I don't know how to continue. ...
0
votes
1answer
1k views

Mathematical Induction Factorials, sum r(r!) =(n+1)! -1 [duplicate]

How do I prove that $$\sum\limits_{r=1}^{n} r(r!) = (n+1)!-1$$ I was able to get to factor: $LHS = k(k!) + (k+1)(k+1)!$ $\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\, RHS = (k+2)! -1$
0
votes
0answers
113 views

Probability Proof by Induction

How can I prove with induction that if one of two events can occur on any given day, $A$ and $B$, and given that if one occurs on one day, the probability that it occurs again on the next day is $1-p$ ...
0
votes
1answer
46 views

Solve non-linear recurrence

I am trying to solve the following recurrence (i.e. determine $a_n$). I'm not entirely sure how to proceed, I have only encountered linear ones so far. This is not a homework, I'm just doing it for ...
1
vote
1answer
21 views

Stochastics with induction

prove that for all $n \in \mathbb{N}$: $\sum_{r=0}^n \binom{n}{r}(-1)^{r} = 0$. The base step is easy, i only get lots of problems when i try to mess with the sum boundries.... so far i've tried: ...
2
votes
2answers
66 views

Induction: $2^n = \sum_{v=0}^{n} \binom{n}{v}$ [duplicate]

I have to prove the following identity for $n \in \mathbb{N}$: $\displaystyle 2^n = \sum_{v=0}^{n} \binom{n}{v}$ Is there a way to show it through induction? Or is there a easier way? My steps so ...
1
vote
0answers
68 views

Induction in the caculus of terms - Mathematical Logic

I'm studying logic from the Ebbinghaus's book "Mathematical Logic" and when I tried to solve some of the exercises doubt rises. Given a calculus C consisting of the following rules: ...
1
vote
3answers
377 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
60 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 ...
2
votes
3answers
142 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
97 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 ...
3
votes
4answers
164 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$ ...
1
vote
5answers
94 views

Prove that for every $n∈N$ the expression is divisible by $10$?

Prove by induction: $3^{(4n+2)} + 1$ is divisible by $10$. My basic step: $3^{(4n+2)} + 1$, where $n = 1$ gives me $3^6 + 1 = 730$, which is divisible by $10$. However, then I have to do the ...
3
votes
3answers
94 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
240 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 ...
1
vote
1answer
55 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.
1
vote
3answers
80 views

Proof by induction proof by using positive numbers n

I was able to prove by induction, that for $k=1$, $\frac{d}{dx} e^{kx} = ke^{kx}$. Assuming the rule is true for $k=n$, I am supposed to show that the rule is true for $ k = n+1$ I have no idea ...
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
2answers
178 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
1answer
72 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 ...
0
votes
2answers
266 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}$ ...
10
votes
1answer
114 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 ...
1
vote
1answer
111 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 ...
0
votes
1answer
93 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 ...
4
votes
1answer
59 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 ...
2
votes
1answer
165 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 ...
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 ...
3
votes
3answers
78 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
146 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
117 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
78 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
2k 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
654 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 ...
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). ...
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
171 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
111 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
189 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
79 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 ...