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
4answers
185 views

Prove by induction that for all natural numbers, n, either 3|n or 3|n+1 or 3|n+2? [closed]

That is prove that for all natural numbers, n, either 3 is a factor of n or n+1 or n+2
2
votes
3answers
85 views

How do you solve a recurrence with a summation function inside

Show that $$t(n) = 1 + \sum_{ j=0}^{n-1} t(j)$$ is the same as $$t(n) = 2^n$$ Initial condition $t(0) = 1$
1
vote
5answers
179 views

Showing “$30$ divides $n^5-n$ for all $n\in\Bbb N$” using induction

Prove that $(n^5 - n)$ divides by $30$ for every $ n\in N$, using induction only. How on earth do I do that? Thing is $(n^5 - n)$ can't be opened using any known formula...
0
votes
1answer
453 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
3answers
214 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: ...
0
votes
2answers
127 views

Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...
6
votes
5answers
301 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
0
votes
1answer
72 views

Limit induction proof

I need help to verify the following Prove that if does not equal 0 lim of x approaches a: x^-n = a^-n I know to prove lim of x approaches a: x^n = a^n requires induction so I believe that this ...
0
votes
3answers
71 views

Show $\sin (x + 180n)$ = $sin \cdot (-1)^n$ for integers n > 0

I have two questions: 1) When we assume $n = k$ true, what is the restriction on integer k? I have been told k does not include the first case of n we tested for i.e. k > 1 which makes sense as n = k ...
0
votes
0answers
24 views

Dividing people into teams of 4 or 7 using induction. [duplicate]

This is a question my friend gave me. I tried to solve it but failed badly. Anyone care to help solve it for me please? A group of n >= 1 people can be divided into teams, each containing either 4 or ...
4
votes
2answers
81 views

Prove by mathematical induction that $\sum_{i=1}^{n}\frac{i}{2^i}\leq2$ for $n\ge 1$

I have this exercise by my professor that I have no idea how to solve. Any help would be greatly appreciated: Using the method of mathematical induction show that for all $n \geq 1$, $n ...
2
votes
2answers
36 views

Standard inductive problem

Question: Prove that $2^n \geq (n+1)^2$ for all $n \geq 6$. I have tried to prove this below and I'm interested if my method was correct and if there is a simpler answer since my answer seems ...
-1
votes
1answer
90 views

Prove that $f(mx)=mf(x)$ for all $x\in\mathbb{R} $ and $m\in\mathbb{Z} $ [closed]

Suppose that $f \colon\mathbb{R}\to \mathbb{R}$ satisfies the functional equation $f(u+v) = f(u)+f(v)$ for all $u,v \in\mathbb{R} $. Prove that $f(mx)=mf(x)$ for all $x\in\mathbb{R} $ and ...
1
vote
2answers
112 views

Using the Invariant Principle to prove a coordinate can't be reached

The problem is as follows: A robot wanders around a 2-dimensional grid. Starting at (0, 0) he is allowed 4 different kinds of step: 1. (+2, -1) 2. (+1, -2) 3. (+1, +1) 4. (-3, 0) He is trying to get ...
6
votes
2answers
1k views

Vandermonde determinant by induction

The determinant at the top-left of the page can be done by induction, it says show that. I have done this before, if I submit this will I get marks? MORE IMPORTANTLY how do I do it by induction? The ...
1
vote
3answers
199 views

Help with Induction problem?

I'm not sure where to start on this induction problem. It is: A group of n >= 1 people can be divided into teams, each containing either 4 or 7 people. What are all possible values of n? Use ...
1
vote
2answers
89 views

Prove $ \sum_{1\leq k < n} k^{\underline{m}}=\frac{n^{\underline{m+1}}}{m+1} $ by induction on $m$

I want to prove by induction the following sum: $$ \sum_{1\leq k < n} k^{\underline{m}}=\frac{n^{\underline{m+1}}}{m+1} $$ but induction should be on $m$. Any hint will be helpful. EDIT: $ ...
1
vote
1answer
66 views

Induction on natural numbers

My textbook, Logic and Discrete Mathematics by Grassman and Tremblay, has an example which I can't wrap my head around (example 3.4; page 127). It shows that for all $n$, $2(n+2)\le(n+2)^2$. As the ...
-2
votes
2answers
94 views

Mathematical induction or what ??

Simplify $$\left(x+\frac1x\right)\left(x^2+\frac1{x^2}\right)\left(x^4+\frac1{x^4}\right)\ldots\left(x^{2^{n-1}}+\frac1{x^{2^{n-1}}}\right)$$ for $n\in\Bbb N$. how to solve this problem, and am I ...
2
votes
4answers
3k views

Help with Induction proof on Fibonacci sequence?

I can't seem to solve this problem. It is: The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows: $F(0) ::= 0$ $F(1) ::= 1$ $F(n) ::= F(n-1) + F(n-2)\qquad(\forall n \ge 2 $) ...
2
votes
1answer
48 views

Defining an inductive set

I'm having some difficulties solving an induction task. Here is the task i'm working on: Give an inductive definition of the given language below: $\{(ab)^n\mid n\in\{0,1,2,\dots\}\} = ...
3
votes
2answers
83 views

Prove by induction that $n < 2 ^n $ where $n \in \mathbb{N}$ [duplicate]

Example question in a textbook that I don't understand. Proof works for n = 1 Setting for k makes $k < 2^k $ Setting for k + 1 makes $k+1 < 2^{k+1} $. Here, I would be stuck, the book ...
-11
votes
2answers
333 views

How can I show that by induction?

I have asked that question - Dividing square of 2013x2013 - and I receive useful answer, which was correct, of course, but because solution of that exercise is my homework I have to have an accurate ...
2
votes
3answers
172 views

Proving that $n!≤((n+1)/2)^n$ by induction

I'm new to inequalities in mathematical induction and don't know how to proceed further. So far I was able to do this: $V(1): 1≤1 \text{ true}$ $V(n): n!≤((n+1)/2)^n$ $V(n+1): ...
1
vote
0answers
67 views

How to solve a inductively defined set?

I'm new to induction. Right now iIm working on a task which I'm not sure if I've solved it correctly. Here is the task: Give an inductive definition of the given language below: ...
1
vote
2answers
30 views

$4$ and $a_{2n + 1}$ are coprime?

Suppose $a_i$ is a sequence of positive integers. Define $a_1 = 1$, $a_2 = 2$ and $a_{n+1} = 2a_n + a_{n-1}$. Does it follow that $$ \gcd(a_{2n+1} , 4 ) = 1 $$ ??? Im trying to see this by ...
1
vote
1answer
90 views

Inductive definition of a given language

I'm having some difficulties solving a induction task. Here is the task i'm working on: Give an inductive definition of the given language below: $\{a^n,b^n\mid ...
2
votes
1answer
58 views

Induction and Countable Set

Ok well everytime ive seen induction being used, its been on the naturals for a statement we wish to prove. My question is would any countable set also work? Hence, doing induction on the rationals as ...
0
votes
1answer
65 views

Mathematical Induction Can't get past base step… Please help

The Question: For all integers $n ≥ 1$ prove $1+2^1 +2^2 +\dots+2^n = 2^{n+1} −1$. I am having a hard time with this. when I let $n=1$, my base step is false. What do I do now?
0
votes
1answer
129 views

Proving Lucas Identity by Induction

I am trying to prove the following identity (I decided to use induction, but if that's not the best way feel free to mention that in the answers): $$L^2_n = 5F^2_n + 4(-1)^n \space\space ...
1
vote
3answers
150 views

Prove some divisibility results by induction

Please hint me, I have two questions: Prove by induction that: 1) $$ {13}^n+7^n+19^n=39k,\,\, n\in\mathbb O$$ in which $\mathbb O$ is the set of odd natural numbers. 2) $$ ...
4
votes
3answers
61 views

Proof by induction that $\sum_{i=1}^n \frac{i}{(i+1)!}=1- \frac{1}{(n+1)!}$

Prove via induction that$\sum_{i=1}^n \frac{i}{(i+1)!}=1- \frac{1}{(n+1)!}$ Having a very difficult time with this proof, have done pages of work but I keep ending up with 1/(k+2). Not sure when to ...
0
votes
0answers
99 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
2
votes
1answer
127 views

Fibonacci Sequence Exercise

I need some help checking the following solution. The Fib sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n\geq 2$, $a_{n+1} = a_n + a_{n-1}$. Thus, the sequence begins: 1, 1, 2, 3, 5, 8, ...
0
votes
4answers
275 views

Induction: Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \frac{\sin(nx)\sin((n+1)x)}{\sin(x)}$

Show that $\sin(2x) + \sin(4x) + \ldots+ \sin(2nx) = \dfrac{\sin(nx)\sin((n+1)x)}{\sin(x)}$ I tried to use induction. Base case is easy, but I'm stuck at the induction step (from $k$ to $k+1$). ...
3
votes
2answers
264 views

Prove $\frac{1}{2} + \cos(x) + \cos(2x) + \dots+ \cos(nx) = \frac{\sin(n+\frac{1}{2})x}{2\sin(\frac{1}{2}x)}$ for $x \neq 0, \pm 2\pi, \pm 4\pi,\dots$

I know that this can be proven inductively. However, I can't get passed the trig. I am pretty sure trig identities can show that the expression above is true for $n=0$, and that if the expression ...
0
votes
3answers
43 views

Prove $4^n > 5*n^2$ where $n\geqslant 3$ is a natural number

I've got this problem out of an exercise booklet and I'm not too familiar with proofs. It looks like I'm supposed to use induction, so far I have: Solving a base case, where $n=3$ So, $4^3 > ...
1
vote
2answers
83 views

Induction proof problem

Prove by induction the following statements: (a) $n! > n^3$ for every $n \ge 6$. (b) prove $\frac{(2n)!}{n!2^n}$ is an integer for every $n\geq 1$ I'm quite terrible with induction so any help ...
2
votes
2answers
2k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
0
votes
2answers
89 views

Proof by Math Induction

I have 3 math induction proofs I have been struggling with for a while. I understand how to do summation proofs but these ones, I cant find a general pattern to solve. Please help. 1) $D(n) = {n(n-3) ...
2
votes
5answers
108 views

Given $n \in \mathbb{N}$ prove that a polynomial result gives a natural number.

A friend asked me this question: Prove that for every $n\in \Bbb N$ the next equation result: $\dfrac{n^3}{6}+\dfrac{n^2} {2}+\dfrac{n}{3}$ would be a natural number. My instincts were that i need ...
1
vote
1answer
88 views

Inductive step in the induction: $\sum^{n}_{i=0} q^i = \frac {1-q^{n+1}}{1-q}\times2$

I am trying induction for the following formula: $$\sum^{n}_{i=0} q^i = \frac {1-q^{n+1}}{1-q}\times2$$ I have done the initial step which gives me for $n=1$ for both sites $1+q$ In the inductive ...
3
votes
1answer
5k views

What's the difference between simple induction and strong induction?

I just started to learn induction in my first year course. I'm having a difficult time grasping the concept. I believe I understand the basics but could someone explain the summary of simple induction ...
9
votes
2answers
301 views

What's an induction problem that will be hard to answer with “backwards reasoning?”

I'm currently the teaching assistant for a course that serves as an introduction to rigorous proofs, and I've noticed some of my students have a tendency to try and use a sort of "backwards reasoning" ...
3
votes
2answers
73 views

Prove that $ \left(1-\frac{1}{n}\right)^n > \frac{1}{6} $ for $n\geq 2$

Prove that $ \left(1-\frac{1}{n}\right)^n > \frac{1}{6} $ for $n \in \mathbb{N}$, $ n\ge 2$ Indeed, the affirmation is true even if $n$ is not a natural ($ n\geq 2 $ ) and we can prove it using ...
0
votes
2answers
54 views

Prove $\sum_{i=1}^{n}i\left(\begin{array}{c} n\\ i \end{array}\right)=n2^{n-1}$ using induction.

I have already derived the formula $\sum_{i=1}^{n}i\left(\begin{array}{c}n\\i \end{array}\right)=n2^{n-1}$ directly just by doing some algebraic manipulations to the summand, which is indeed proves ...
1
vote
2answers
84 views

How do I prove $2^{n+1} + 2n + 1 = 2^{n+2} - 1$

I am attempting to prove using induction: $\sum_0^n 2i = 2^{n + 1} - 1$ I have gotten to the point where I need to show: $2^{n+1} + 2n + 1 = 2^{n+2} - 1$ How do I prove this? Or should I be ...
1
vote
0answers
43 views

Show by induction… Help

Let $a,n\in\mathbb{N}$, show that there exists $m\in\mathbb{N}$, such that $(a+1)^n=ma+1$ I tried to do by induction on $n$, but found it a bit strange the demonstration. ...
0
votes
4answers
107 views

Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.

First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up ...
3
votes
2answers
109 views

Let $n \in \Bbb N$. Let $p>2$ a prime number. Show that $1^n+2^n+…+(p-1)^n \equiv 0 \pmod {p}$ [duplicate]

This is an exercise in my abstract algebra reader, in the chapter about polynomial rings. Let $n \in \Bbb N$. Let $p>2$ a prime number. And let $n$ not divisble by $p-1$. Show that ...